// [5/29/2014 Sjm]
/*
对于此题仍属于最大流 多个源点,多个汇点 的题型,不过技巧性增加了。。。
第一想法:
建图方式为:
超级源点 --> 食物 --> 牛 --> 饮料 --> 超级汇点
(注每条连线的容量为 1)
但不幸的是,wa。。。
//////////////////////////////////////////////////////////////////////////////////////////
要注意:
1) Each cow has a preference for certain foods and drinks, and she will consume no others.
2) 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).
这意味着每头牛只能连接一个食物、一个饮料,且被连接的食物和饮料不能被其他牛连接。
//////////////////////////////////////////////////////////////////////////////////////////
而像上面的方法建图,食物流向食物相对应的牛的流量可以 >1, 导致由牛流出的流量 >1, 使一头牛可连接多个饮料。。。
看到一种很厉害的解决办法,将牛一分为二:
超级源点 --> 食物 --> 牛a --> 牛b --> 饮料 --> 超级汇点
(注每条连线的容量为 1)
将一头牛一分为二后,由于牛a和牛b之间的连线的容量为 1,,故而
尽管由食物可以流向牛a的流量 >1 ,但在由牛b流向饮料的流量被限制为了 1,解决了上面问题。
*/
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstdio>
4 #include <vector>
5 #include <algorithm>
6 #include <cstring>
7 using namespace std;
8 const int MAX_V = 410;
9 const int INF = 0x3f3f3f3f;
10 int N, F, D;
11
12 struct edge{ int to, cap, rev; };
13 vector<edge> G[MAX_V];
14 bool used[MAX_V];
15
16 void Add_edge(int from, int to, int cap)
17 {
18 edge e1 = { to, cap, G[to].size() };
19 G[from].push_back(e1);
20 edge e2 = { from, 0, G[from].size() - 1 };
21 G[to].push_back(e2);
22 }
23
24 int Dfs(int v, int t, int f)
25 {
26 if (v == t) return f;
27 used[v] = true;
28 for (int i = 0; i < G[v].size(); i++) {
29 edge &e = G[v][i];
30 if (!used[e.to] && e.cap > 0) {
31 int d = Dfs(e.to, t, min(f, e.cap));
32 if (d > 0) {
33 e.cap -= d;
34 G[e.to][e.rev].cap += d;
35 return d;
36 }
37 }
38 }
39 return 0;
40 }
41
42 int Max_flow(int s, int t)
43 {
44 int flow = 0;
45 for (;;) {
46 memset(used, 0, sizeof(used));
47 int f = Dfs(s, t, INF);
48 if (!f) { return flow; }
49 flow += f;
50 }
51 }
52
53 int main()
54 {
55 //freopen("input.txt", "r", stdin);
56 //freopen("output.txt", "w", stdout);
57 while (~scanf("%d %d %d", &N, &F, &D))
58 {
59 int f_num, d_num;
60 for (int i = 1; i <= N; i++) {
61 Add_edge(i, N + i, 1); // 将 牛 一分为二
62 scanf("%d %d", &f_num, &d_num);
63 int t_f, t_d;
64 for (int j = 1; j <= f_num; j++) {
65 scanf("%d", &t_f);
66 Add_edge(2 * N + t_f, i, 1); // 食物 --> 食物相对应的牛
67 }
68 for (int k = 1; k <= d_num; k++) {
69 scanf("%d", &t_d);
70 Add_edge(N + i, 2 * N + F + t_d, 1); // 牛 --> 牛相对应的饮料
71 }
72 }
73 for (int i = 2 * N + 1; i <= 2 * N + F; i++) {
74 Add_edge(0, i, 1); // 超级源点 --> 每一种食物
75 }
76 for (int i = 2 * N + F + 1; i <= 2 * N + F + D; i++) {
77 Add_edge(i, 2 * N + F + D + 1, 1); // 每一种饮料 --> 超级汇点
78 }
79 printf("%d
", Max_flow(0, 2 * N + F + D + 1));
80 for (int i = 0; i <= 2 * N + F + D + 1; i++) {
81 G[i].clear();
82 }
83 }
84 return 0;
85 }