hdu-4292.food(类dining网络流建图)

Food

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9289    Accepted Submission(s): 3019


Problem Description
　　You, a part-time dining service worker in your college’s dining hall, are now confused with a new problem: serve as many people as possible.
　　The issue comes up as people in your college are more and more difficult to serve with meal: They eat only some certain kinds of food and drink, and with requirement unsatisfied, go away directly.
　　You have prepared F (1 <= F <= 200) kinds of food and D (1 <= D <= 200) kinds of drink. Each kind of food or drink has certain amount, that is, how many people could this food or drink serve. Besides, You know there’re N (1 <= N <= 200) people and you too can tell people’s personal preference for food and drink.
　　Back to your goal: to serve as many people as possible. So you must decide a plan where some people are served while requirements of the rest of them are unmet. You should notice that, when one’s requirement is unmet, he/she would just go away, refusing any service.
 
Input
　　There are several test cases.
　　For each test case, the first line contains three numbers: N,F,D, denoting the number of people, food, and drink.
　　The second line contains F integers, the ith number of which denotes amount of representative food.
　　The third line contains D integers, the ith number of which denotes amount of representative drink.
　　Following is N line, each consisting of a string of length F. �e jth character in the ith one of these lines denotes whether people i would accept food j. “Y” for yes and “N” for no.
　　Following is N line, each consisting of a string of length D. �e jth character in the ith one of these lines denotes whether people i would accept drink j. “Y” for yes and “N” for no.
　　Please process until EOF (End Of File).
 
Output
　　For each test case, please print a single line with one integer, the maximum number of people to be satisfied.
 
Sample Input
4 3 3 1 1 1 1 1 1 YYN NYY YNY YNY YNY YYN YYN NNY
 
Sample Output
3
 
Source
2012 ACM/ICPC Asia Regional Chengdu Online
如果你做过poj3281你应该清除他们很像，如果你没做过可以选择先看看那道更简单一点的题目。
 
这道题告诉我以后每个最大流都自己手写算法吧，我是真的捞。。。一发AC的题，结果因为感觉这个题太模版，就把做的上个无向图最大流的题代码粘贴过来了，然后就？？？直到临睡才想起无向图，我傻逼了......就是个建图，都在代码里了。。
下面这是我自己写的第一种做法，建立很多多余的节点，因为我想着需要结点容量限制，所以每个结点都拆了，做完之后看别人的代码发现原来可以有更简单的建图方法，那么看最后吧。
  1 /*
  2     结点0 ~ n - 1存左牛结点
  3     结点n ~ 2 * n - 1存右牛结点
  4     结点2 * n ~ 2 * n + f - 1存左食物
  5     结点2 * n + f ~ 2 * n + f * 2 - 1存右食物
  6     结点2 * n + 2 * f ~ 2 * n + 2 * f + d - 1存饮料左
  7     结点2 * n + 2 * f + d ~ 2 * n + 2 * f + d * 2 - 1存饮料右
  8     结点2 * n + 2 * f + 2 * d为s，t = s = 1。
  9 */
 10 
 11 #include <cstdio>
 12 #include <cstring>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 const int maxn = 200 + 5, maxm = 1000 * 1000 + 5, inf = 0x3f3f3f3f;
 17 int numf[maxn], numd[maxn];
 18 char str[maxn];
 19 
 20 int tot, head[maxn << 3], que[maxn << 3], dep[maxn << 3], cur[maxn << 3], sta[maxn << 3];
 21 
 22 struct Edge {
 23     int to, cap, flow, next, from;
 24 } edge[maxm << 1];
 25 
 26 void init() {
 27     tot = 2;
 28     memset(head, -1, sizeof head);
 29 }
 30 
 31 void addedge(int u, int v, int w) {
 32     edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = 0; edge[tot].from = u;
 33     edge[tot].next = head[u]; head[u] = tot ++;
 34     edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0; edge[tot].from = v;
 35     edge[tot].next = head[v]; head[v] = tot ++;
 36 }
 37 
 38 bool bfs(int s, int t, int n) {
 39     memset(dep, -1, sizeof dep[0] * (n + 1));
 40     int front = 0, tail = 0;
 41     dep[s] = 0;
 42     que[tail ++] = s;
 43     while(front < tail) {
 44         int u = que[front ++];
 45         for(int i = head[u]; ~i; i = edge[i].next) {
 46             int v = edge[i].to;
 47             if(edge[i].cap > edge[i].flow && dep[v] == -1) {
 48                 dep[v] = dep[u] + 1;
 49                 if(v == t) return true;
 50                 que[tail ++] = v;
 51             }
 52         }
 53     }
 54     return false;
 55 }
 56 
 57 int dinic(int s, int t, int n) {
 58     int maxflow = 0;
 59     while(bfs(s, t, n)) {
 60         for(int i = 0; i <= n; i ++) cur[i] = head[i];
 61         int u = s, tail = 0;
 62         while(~cur[s]) {
 63             if(u == t) {
 64                 int tp = inf;
 65                 for(int i = tail - 1; i >= 0; i --)
 66                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
 67                 maxflow += tp;
 68                 for(int i = tail - 1; i >= 0; i --) {
 69                     edge[sta[i]].flow += tp;
 70                     edge[sta[i] ^ 1].flow -= tp;
 71                     if(edge[sta[i]].cap - edge[sta[i]].flow == 0)   tail = i;
 72                 }
 73                 u = edge[sta[tail] ^ 1].to;
 74             } else if(~ cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
 75                 sta[tail ++] = cur[u];
 76                 u = edge[cur[u]].to;
 77             } else {
 78                 while(u != s && cur[u] == -1)
 79                     u = edge[sta[-- tail] ^ 1].to;
 80                 cur[u] = edge[cur[u]].next;
 81             }
 82         }
 83     }
 84     return maxflow;
 85 }
 86 
 87 int main() {
 88     int n, f, d;
 89     while(~scanf("%d %d %d", &n, &f, &d)) {
 90         init();
 91         int s = 2 * n + 2 * f + d * 2, t = s + 1;//超级源点和超级汇点
 92         for(int i = 0; i < f; i ++) {
 93             scanf("%d", &numf[i]);
 94             addedge(s, 2 * n + i, inf);//超级源点到食物左
 95             addedge(2 * n + i, 2 * n + f + i, numf[i]);//食物左到食物右
 96         }
 97         for(int i = 0; i < d; i ++) {
 98             scanf("%d", &numd[i]);
 99             addedge(2 * n + 2 * f + i, 2 * n + 2 * f + d + i, numd[i]);//饮料左到饮料右
100             addedge(2 * n + 2 * f + d + i, t, inf);//饮料右到超级汇点
101         }
102         for(int i = 0; i < n; i ++) {
103             addedge(i, n + i, 1);//左牛到右牛
104         }
105         for(int i = 0; i < n; i++) {
106             scanf("%s", str);
107             for(int j = 0; j < f; j ++) {
108                 if(str[j] == 'Y')   
109                     addedge(2 * n + f + j, i, 1);//从食物右到左牛
110             }
111         }
112         for(int i = 0; i < n; i ++) {
113             scanf("%s", str);
114             for(int j = 0; j < d; j ++) {
115                 if(str[j] == 'Y')
116                     addedge(n + i, 2 * n + 2 * f + j, 1);//从右牛到左饮料
117             }
118         }
119         // for(int i = 2; i <= tot; i ++) {
120         //     printf("%d -> %d
", edge[i].from, edge[i].to);
121         // }
122         printf("%d
", dinic(s, t, 2 * n + 2 * f + 2 * d + 2));
123     }
124     return 0;
125 }

下面这种建图方法和上面的类似，只是上图是拆点限制点流量，而我们知道对于每一件食物，如果我们有一个人选取它，那么它必定是只选取了一件，因为后面拆点n决定的，那么也就是每个人只能取他所喜欢食物中的一种中的一个，所以我们只需要对我们能够提供的某种食物限量就可以了，也就是从源点到某种食物权值为food_num，这样就可以限制住每种食物的用量了，接着看饮料，如果某个人选取了一个饮料，那么他也只能选取这一种饮料中的一瓶，因为前面已经对n拆点导致它能扩展的流也只有1，所以导致她选的饮料也是1对1，所以想要限制饮料的个数，也只需要无限索取，直到最后无法流到汇点就ok，那也就是从饮料到汇点权值为drink_num。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 const int maxn = 200 + 5, maxm = 1000 * 1000 + 5, inf = 0x3f3f3f3f;
  7 int numf[maxn], numd[maxn];
  8 char str[maxn];
  9 
 10 int tot, head[maxn << 3], que[maxn << 3], dep[maxn << 3], cur[maxn << 3], sta[maxn << 3];
 11 
 12 struct Edge {
 13     int to, cap, flow, next, from;
 14 } edge[maxm << 1];
 15 
 16 void init() {
 17     tot = 2;
 18     memset(head, -1, sizeof head);
 19 }
 20 
 21 void addedge(int u, int v, int w) {
 22     edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = 0; edge[tot].from = u;
 23     edge[tot].next = head[u]; head[u] = tot ++;
 24     edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0; edge[tot].from = v;
 25     edge[tot].next = head[v]; head[v] = tot ++;
 26 }
 27 
 28 bool bfs(int s, int t, int n) {
 29     memset(dep, -1, sizeof dep[0] * (n + 1));
 30     int front = 0, tail = 0;
 31     dep[s] = 0;
 32     que[tail ++] = s;
 33     while(front < tail) {
 34         int u = que[front ++];
 35         for(int i = head[u]; ~i; i = edge[i].next) {
 36             int v = edge[i].to;
 37             if(edge[i].cap > edge[i].flow && dep[v] == -1) {
 38                 dep[v] = dep[u] + 1;
 39                 if(v == t) return true;
 40                 que[tail ++] = v;
 41             }
 42         }
 43     }
 44     return false;
 45 }
 46 
 47 int dinic(int s, int t, int n) {
 48     int maxflow = 0;
 49     while(bfs(s, t, n)) {
 50         for(int i = 0; i <= n; i ++) cur[i] = head[i];
 51         int u = s, tail = 0;
 52         while(~cur[s]) {
 53             if(u == t) {
 54                 int tp = inf;
 55                 for(int i = tail - 1; i >= 0; i --)
 56                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
 57                 maxflow += tp;
 58                 for(int i = tail - 1; i >= 0; i --) {
 59                     edge[sta[i]].flow += tp;
 60                     edge[sta[i] ^ 1].flow -= tp;
 61                     if(edge[sta[i]].cap - edge[sta[i]].flow == 0)   tail = i;
 62                 }
 63                 u = edge[sta[tail] ^ 1].to;
 64             } else if(~ cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
 65                 sta[tail ++] = cur[u];
 66                 u = edge[cur[u]].to;
 67             } else {
 68                 while(u != s && cur[u] == -1)
 69                     u = edge[sta[-- tail] ^ 1].to;
 70                 cur[u] = edge[cur[u]].next;
 71             }
 72         }
 73     }
 74     return maxflow;
 75 }
 76 
 77 int main() {
 78     int n, f, d;
 79     while(~scanf("%d %d %d", &n, &f, &d)) {
 80         init();
 81         int s = 2 * n + f + d, t = s + 1;//超级源点和超级汇点
 82         for(int i = 0; i < f; i ++) {
 83             scanf("%d", &numf[i]);
 84             addedge(s, n * 2 + i, numf[i]);
 85         }
 86         for(int i = 0; i < d; i ++) {
 87             scanf("%d", &numd[i]);
 88             addedge(n * 2 + f + i, t, numd[i]);
 89         }
 90         for(int i = 0; i < n; i++) {
 91             addedge(i, n + i, 1);//左牛到右牛
 92             scanf("%s", str);
 93             for(int j = 0; j < f; j ++) {
 94                 if(str[j] == 'Y')
 95                     addedge(2 * n + j, i, 1);
 96             }
 97         }
 98         for(int i = 0; i < n; i ++) {
 99             scanf("%s", str);
100             for(int j = 0; j < d; j ++) {
101                 if(str[j] == 'Y')
102                     addedge(n + i, 2 * n + f + j, 1);//从右牛到饮料
103             }
104         }
105         // for(int i = 2; i <= tot; i ++) {
106         //     printf("%d -> %d
", edge[i].from, edge[i].to);
107         // }
108         printf("%d
", dinic(s, t, 2 * n + f + d + 2));
109     }
110     return 0;
111 }

不得不承认这种做法确实节省了很多空间呀。

 
 
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bianjunting/p/11403334.html