【題意】：給出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