农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料. 农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N (1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料. 每一件食物和饮料只能由一头牛来用. 例如如果食物2被一头牛吃掉了,没有别的牛能吃食物2.

* 第一行: 三个数: N, F, 和 D

* 第2..N+1行: 每一行由两个数开始F_i 和 D_i, 分别是第i 头牛可以吃的食品数和可以喝的饮料数.下F_i个整数是第i头牛可以吃的食品号,再下面的D_i个整数是第i头牛可以喝的饮料号码.

* 第一行: 一个整数,最多可以喂饱的牛数.

Gold

  1 #include <cstdio>  2   3 inline int nextChar(void) {  4     const int siz = 1024;  5       6     static char buf[siz];  7     static char *hd = buf + siz;  8     static char *tl = buf + siz;  9      10     if (hd == tl) 11         fread(hd = buf, 1, siz, stdin); 12          13     return *hd++; 14 } 15   16 inline int nextInt(void) { 17     register int ret = 0; 18     register int neg = false; 19     register int bit = nextChar(); 20      21     for (; bit < 48; bit = nextChar()) 22         if (bit == ‘-‘)neg ^= true; 23          24     for (; bit > 47; bit = nextChar()) 25         ret = ret * 10 + bit - 48; 26          27     return neg ? -ret : ret; 28 } 29  30 inline int min(int a, int b) 31 { 32     return a < b ? a : b; 33 } 34  35 const int siz = 500005; 36 const int inf = 1000000007; 37  38 int tot; 39 int s, t; 40 int hd[siz]; 41 int to[siz]; 42 int fl[siz]; 43 int nt[siz]; 44  45 inline void add(int u, int v, int f) 46 { 47     nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; hd[u] = tot++; 48     nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; hd[v] = tot++; 49 } 50  51 int dep[siz]; 52  53 inline bool bfs(void) 54 { 55     static int que[siz], head, tail; 56      57     for (int i = s; i <= t; ++i)dep[i] = 0; 58      59     dep[que[head = 0] = s] = tail = 1; 60      61     while (head != tail) 62     { 63         int u = que[head++], v; 64          65         for (int i = hd[u]; ~i; i = nt[i]) 66             if (!dep[v = to[i]] && fl[i]) 67                 dep[que[tail++] = v] = dep[u] + 1; 68     } 69      70     return dep[t]; 71 } 72  73 int cur[siz]; 74  75 int dfs(int u, int f) 76 { 77     if (u == t || !f) 78         return f; 79          80     int used = 0, flow, v; 81      82     for (int i = cur[u]; ~i; i = nt[i]) 83         if (dep[v = to[i]] == dep[u] + 1 && fl[i]) 84         { 85             flow = dfs(v, min(fl[i], f - used)); 86              87             used += flow; 88             fl[i] -= flow; 89             fl[i^1] += flow; 90              91             if (used == f) 92                 return f; 93              94             if (fl[i]) 95                 cur[u] = i; 96         } 97          98     if (!used) 99         dep[u] = 0;100     101     return used;102 }103 104 inline int maxFlow(void)105 {106     int maxFlow = 0, newFlow;107     108     while (bfs())109     {110         for (int i = s; i <= t; ++i)111             cur[i] = hd[i];112         113         while (newFlow = dfs(s, inf))114             maxFlow += newFlow;115     }116     117     return maxFlow;118 }119 120 int N, F, D;121 122 inline int cow(int x, int y)123 {124     return F + D + y * N + x;125 }126 127 inline int food(int x)128 {129     return x;130 }131 132 inline int drink(int x)133 {134     return x + F;135 }136 137 signed main(void)138 {139     N = nextInt();140     F = nextInt();141     D = nextInt();142     143     s = 0, t = N*2 + F + D + 1;144     145     for (int i = s; i <= t; ++i)146         hd[i] = -1;147         148     for (int i = 1; i <= F; ++i)149         add(s, food(i), 1);150         151     for (int i = 1; i <= D; ++i)152         add(drink(i), t, 1);153         154     for (int i = 1; i <= N; ++i)155     {156         int f = nextInt();157         int d = nextInt();158         159         add(cow(i, 0), cow(i, 1), 1);160         161         for (int j = 1; j <= f; ++j)162             add(food(nextInt()), cow(i, 0), 1);163         164         for (int j = 1; j <= d; ++j)165             add(cow(i, 1), drink(nextInt()), 1);166     }167     168     printf("%d\n", maxFlow());169 }