题目描述
Description
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
Sample 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
Sample Output
3
Hint
One way to satisfy three cows is:
Cow 1: no meal
Cow 2: Food #2, Drink #2
Cow 3: Food #1, Drink #1
Cow 4: Food #3, Drink #3
The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.
题目链接
http://poj.org/problem?id=3281
解题思路
题意是说有n头牛，f种食物和d种饮料，每种食物和饮料数量都是1。每头牛都有自己喜欢的食物和饮料，问要怎么分配食物和饮料才能使得尽量多的牛都能得到自己喜欢的。
经典的网络流拆点问题，但是由于刚刚接触网络流算法，对他的思想理解的还不是很深。这类题目的难点就是模型的建立，如何构造一个合理的图，然后执行网络流算法得出正确结论。下面就先说一下这题的建图思路：
普通建图一般都是源点与供应相连接，汇点与需求相连接，可是此题中有两种供应食物和饮料。因为只有牛与食物和饮料都有关系，而食物和饮料之间没有必然联系，所以可以用牛将这两种供应串起来，即建图就变为：源点->食物->牛->饮料->汇点。可是为什么不是将源点与牛相连，牛与食物和饮料相连呢？因为一旦是这种连法的话，即：源点->牛->食物和饮料->汇点，这样的话就会导致多头牛用到同一个食物。
如果要是按照源点->食物->牛->饮料->汇点这样建图的话，还有一点点小问题，就是会发生同一头牛对应多种食物和多种水的情况下，会有多条路成立，导致了结果的错误。所以，要将拆点：源点->食物->牛->牛->饮料->汇点，将牛和牛的权值设为1，这样，一旦有一条路成立，这条权值为1的边就会占用，这样其他的和这头牛对应的路就不会算在内了。
AC代码
220K/16MS/C++1
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
using namespace std;
int N, F, D;
const int maxn = 100005;
struct Edge
{
int to, c, next;
} e[maxn * 4];
int st, ed, cnt;
int head[1000];
void add(int a, int b, int c)
{
e[cnt].to = b;
e[cnt].c = c;
e[cnt].next = head[a];
head[a] = cnt++;
e[cnt].to = a;
e[cnt].c = 0;
e[cnt].next = head[b];
head[b] = cnt++;
}
int vis[1000], dis[1000];
int cur[1000];
bool BFS()
{
memset(dis, -1, sizeof(dis));
dis[st] = 0;
queue<int> que;
que.push(st);
while (!que.empty())
{
int j = que.front();
que.pop();
for (int k = head[j]; k != -1; k = e[k].next)
{
int i = e[k].to;
if (dis[i] == -1 && e[k].c)
{
dis[i] = dis[j] + 1 ;
que.push(i);
if(i == ed) return true;
}
}
}
return false;
}
int DFS(int x, int mx)
{
if (x == ed || mx == 0) return mx;
int f, flow = 0;
for (int& i = cur[x]; i != -1; i = e[i].next)
{
if (dis[x] + 1 == dis[e[i].to] && (f = DFS(e[i].to, min(mx, e[i].c))))
{
e[i].c -= f;
e[i ^ 1].c += f;
flow += f;
mx -= f;
if (!mx) break;
}
}
return flow;
}
int dinic()
{
int tmp = 0;
int maxflow = 0;
while (BFS())
{
for (int i = st; i <= ed; i++)
cur[i] = head[i];
while (tmp = DFS(st, inf))
maxflow += tmp;
}
return maxflow;
}
int main()
{
int food, drink, x;
while (~scanf("%d%d%d", &N, &F, &D))
{
st = 0;
ed = F + N * 2 + D + 1;
cnt = 0;
memset(head, -1, sizeof(head));
for (int i = 1; i <= N; i++)
{
scanf("%d%d", &food, &drink);
for (int j = 1; j <= food; j++)
{
scanf("%d", &x);
add(x, F + i, 1);
}
for (int j = 1; j <= drink; j++)
{
scanf("%d", &x);
add(F + N + i, F + N * 2 + x, 1);
}
}
for (int i = 1; i <= F; i++)
{
add(st, i, 1);
}
for (int i = 1; i <= D; i++)
{
add(F + N * 2 + i, ed, 1);
}
for (int i = 1; i <= N; i++)
{
add(F + i, F + N + i, 1);
}
printf("%d\n", dinic());
}
return 0;
}