题目
Description
2000MS/65536K
Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.
Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.
Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.
Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).
Input
Line 1: Three space-separated integers: N, F, and D
Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.
Output
Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes
Simple input
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
Simple output
3
题目分析
这道题可以算的上是一道网络流的模板题，大意是有N头牛F种食物和D种饮料，每头牛喜欢的饮料和食物在输入中给出，所有的编号按1-F和1-D来排列，求最多可以为多少头牛进行匹配。其实一开始我认为可以用二分图来做，将饮料和食物打包成为一个点，但是发现搞不了，于是就想到了网络流的最大流。将食物与牛相连，牛再与饮料相连，最后求得最大的匹配数，可是这里需要将牛拆分成为两个点，并且将两个点之间的容量设为1，这是为了防止残量网络生成返回路径导致一牛对多食物对多饮料的情况出现，建好图之后再裸一个dinic算法即可搞出。
AC代码
924K/16MS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define inf 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int NV=20005;
const int NE=500005;
int he[NV],ecnt;
int src,sink;
struct edge
{
int v,next,f;
} E[2*NE];
void adde(int u,int v,int c)
{
E[++ecnt].v=v;
E[ecnt].f=c;
E[ecnt].next=he[u];
he[u]=ecnt;
E[++ecnt].v=u;
E[ecnt].f=0;
E[ecnt].next=he[v];
he[v]=ecnt;
}
void init()
{
ecnt=0;
memset(he,-1,sizeof(he));
}
queue<int> que;
bool vis[NV];
int dis[NV];
void bfs()
{
memset(dis,0,sizeof(dis));
while(!que.empty()) que.pop();
vis[src]=1;
que.push(src);
while(!que.empty())
{
int u=que.front();
que.pop();
for (int i=he[u]; i!=-1; i=E[i].next)
if (E[i].f&&!vis[E[i].v])
{
que.push(E[i].v);
dis[E[i].v]=dis[u]+1;
vis[E[i].v]=1;
}
}
}
int dfs(int u,int delta)
{
if (u==sink)
return delta;
else
{
int ret=0;
for (int i=he[u]; delta&&i!=-1; i=E[i].next)
if (E[i].f&&dis[E[i].v]==dis[u]+1)
{
int dd=dfs(E[i].v,min(E[i].f,delta));
E[i].f-=dd;
E[(i+1)^1-1].f+=dd;
delta-=dd;
ret+=dd;
}
return ret;
}
}
int maxflow()
{
int ret=0;
while(1)
{
memset(vis,0,sizeof(vis));
bfs();
if (!vis[sink]) return ret;
ret+=dfs(src,inf);
}
}
int main()
{
int n,f,d;
while(scanf("%d%d%d",&n,&f,&d)!=EOF)
{
init();
int s=0,t=n+n+f+d+1;
for(int i=1;i<=n;i++)
{
int temf,temd;
scanf("%d%d",&temf,&temd);
for(int j=1;j<=temf;j++)
{
int a;
scanf("%d",&a);
adde(a,f+i,1);
}
for(int j=1;j<=temd;j++)
{
int b;
scanf("%d",&b);
adde(f+n+i,f+n+n+b,1);
}
}
src=s;
sink=t;
for(int i=1;i<=f;i++)adde(s,i,1);//源点和食物相连
for(int i=1;i<=d;i++)adde(f+n+n+i,t,1);//饮料和汇点相连
for(int i=1;i<=n;i++)adde(f+i,f+n+i,1);//牛和牛相连
printf("%d\n",maxflow());
}
}