1711: [Usaco2007 Open]Dining吃飯

Time Limit: 5 Sec??Memory Limit: 64 MB
Submit: 902??Solved: 476
[Submit][Status][Discuss]

Description

農夫JOHN為牛們做了很好的食品,但是牛吃飯很挑食. 每一頭牛只喜歡吃一些食品和飲料而別的一概不吃.雖然他不一定能把所有牛喂飽,他還是想讓盡可能多的牛吃到他們喜歡的食品和飲料. 農夫JOHN做了F (1 <= F <= 100) 種食品并準備了D (1 <= D <= 100) 種飲料. 他的N (1 <= N <= 100)頭牛都以決定了是否愿意吃某種食物和喝某種飲料. 農夫JOHN想給每一頭牛一種食品和一種飲料,使得盡可能多的牛得到喜歡的食物和飲料. 每一件食物和飲料只能由一頭牛來用. 例如如果食物2被一頭牛吃掉了,沒有別的牛能吃食物2.

Input

* 第一行: 三個數: N, F, 和 D

* 第2..N+1行: 每一行由兩個數開始F_i 和 D_i, 分別是第i 頭牛可以吃的食品數和可以喝的飲料數.下F_i個整數是第i頭牛可以吃的食品號,再下面的D_i個整數是第i頭牛可以喝的飲料號碼.

Output

* 第一行: 一個整數,最多可以喂飽的牛數.

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

輸入解釋:

牛 1: 食品從 {1,2}, 飲料從 {1,2} 中選
牛 2: 食品從 {2,3}, 飲料從 {1,2} 中選
牛 3: 食品從 {1,3}, 飲料從 {1,2} 中選
牛 4: 食品從 {1,3}, 飲料從 {3} 中選

Sample Output

3
輸出解釋:

一個方案是:
Cow 1: 不吃
Cow 2: 食品 #2, 飲料 #2
Cow 3: 食品 #1, 飲料 #1
Cow 4: 食品 #3, 飲料 #3
用鴿籠定理可以推出沒有更好的解 (一共只有3總食品和飲料).當然,別的數據會更難.

HINT

Source

Gold

[Submit][Status][Discuss]

?

網絡流，拆點建圖，每一條流都對應著滿足一頭牛的方案。和今天考試T1賊像……

?

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 }

?

@Author: YouSiki

轉載于:https://www.cnblogs.com/yousiki/p/6253760.html

總結

以上是生活随笔為你收集整理的BZOJ 1711: [Usaco2007 Open]Dining吃饭的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。