【题意】：给出F种食物和D种饮料，每种食物和饮料都只能使用一次。有N只牛，给出每只牛喜欢的食物和饮料，要你合理分配，尽可能让每只牛都得到它喜欢的食物和饮料，问：最多有多少只牛满足条件，即分配到喜欢的食物和饮料。
【题解】：这题是比较明显的最大流，构图也很明显。
考虑到食物和饮料之间本身是没有任何关系的，所以我们通过牛把它们联系起来，即s->food->cow->drink->t.
加入一个源点s，向每个食物连边，容量都为1，表示每个食物只能用一次。
加入一个汇点t，向每个饮料连反向边，容量都为1，理由同上。
然后要把每个牛拆点成 i , i' ，连边i->i'，容量为1，表示每个牛只能分配一种食物和饮料。可以想象一下，不拆点的话牛就有可能同时对应多种食物和饮料。
然后如果牛i喜欢食物food i，就连边food i->i，容量为1，这里容量其实无所谓，inf也可以。
然后如果牛i喜欢饮料drink i，就连边i'->drink i，容量为1，这里容量同样无所谓，inf也可以。
连完每种边就会得到下图的类型：
最后求一次s-t的最大流即可。
【代码】：
1 #include "iostream"
2 #include "cstring"
3 using namespace std;
4 #define maxn 50005
5 #define maxm 2000005
6 #define bigint __int64
7 const bigint INF = 1 << 29;
8
9 typedef struct edge {
10 int u, v;
11 bigint cap, flow;
12 int next;
13 }edge;
14
15 int eh[maxn], tot;
16 edge et[maxm];
17 int gap[maxn], pre[maxn], cur[maxn], dist[maxn], a[maxn];
18 int s, t;
19
20 void add(int u, int v, bigint cap, bigint flow) {
21 edge E = {u, v, cap, flow, eh[u]};
22 et[tot] = E;
23 eh[u] = tot++;
24 }
25
26 void addedge(int u, int v, bigint cap) {
27 add(u, v, cap, 0), add(v, u, 0, 0);
28 }
29
30 void init() {
31 tot = 0;
32 memset(eh, -1, sizeof(eh));
33 }
34
35 bigint min(bigint a, bigint b) {
36 return a < b ? a : b;
37 }
38
39 bigint sap_gap(int s, int t, int n) {
40 int u, v, now;
41 memset(dist, 0, sizeof(dist));
42 memset(a, 0, sizeof(a));
43 for(u = 0; u <= n; u++)
44 cur[u] = eh[u];
45 bigint maxflow = 0;
46 u = s;
47 a[s] = INF, gap[s] = n;
48 while(dist[s] < n) {
49 for(now = cur[u]; now != -1; now = et[now].next)
50 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
51 break;
52 if(now != -1) {
53 cur[u] = pre[v] = now;
54 a[v] = min(a[u], et[now].cap - et[now].flow);
55 u = v;
56 if(u == t) {
57 for(; u != s; u = et[pre[u]].u) {
58 et[pre[u]].flow += a[t];
59 et[pre[u] ^ 1].flow -= a[t];
60 }
61 maxflow += a[t];
62 a[s] = INF;
63 }
64 }
65 else {
66 if(--gap[dist[u]] == 0)
67 break;
68 dist[u] = n;
69 cur[u] = eh[u];
70 for(now = cur[u]; now != -1; now = et[now].next)
71 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
72 dist[u] = dist[et[now].v] + 1;
73 gap[dist[u]]++;
74 if(u != s)
75 u = et[pre[u]].u;
76 }
77 }
78 return maxflow;
79 }
80
81 int main() {
82 int n, f, d;
83 int u, v, i, j;
84 int fn, dn;
85
86 while(cin >> n >> f >> d) {
87 init();
88 s = 0;
89 t = f + d + 2 * n + 1;
90
91 for(i = 1; i <= f; i++)
92 addedge(s, i, 1);
93
94 for(i = 1; i <= d; i++)
95 addedge(f + 2 * n + i, t, 1);
96
97 for(i = 1; i <= n; i++)
98 addedge(f + i, f + n + i, 1);
99
100 for(i = 1; i <= n; i++) {
101 cin >> fn >> dn;
102 for(j = 0; j < fn; j++) {
103 cin >> u;
104 addedge(u, f + i, 1);
105 }
106 for(j = 0; j < dn; j++) {
107 cin >> v;
108 addedge(f + n + i, f + 2 * n + v, 1);
109 }
110 }
111 printf("%I64d\n", sap_gap(s, t, t - s + 1));
112 }
113 return 0;
114 }
115
116
117