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

Source

2012 ACM/ICPC Asia Regional Chengdu Online

如果你做过poj3281你应该清除他们很像，如果你没做过可以选择先看看那道更简单一点的题目。

这道题告诉我以后每个最大流都自己手写算法吧，我是真的捞。。。一发AC的题，结果因为感觉这个题太模版，就把做的上个无向图最大流的题代码粘贴过来了，然后就？？？直到临睡才想起无向图，我傻逼了......就是个建图，都在代码里了。。

下面这是我自己写的第一种做法，建立很多多余的节点，因为我想着需要结点容量限制，所以每个结点都拆了，做完之后看别人的代码发现原来可以有更简单的建图方法，那么看最后吧。

 /*

     结点0 ~ n - 1存左牛结点

     结点n ~ 2 * n - 1存右牛结点

     结点2 * n ~ 2 * n + f - 1存左食物

     结点2 * n + f ~ 2 * n + f * 2 - 1存右食物

     结点2 * n + 2 * f ~ 2 * n + 2 * f + d - 1存饮料左

     结点2 * n + 2 * f + d ~ 2 * n + 2 * f + d * 2 - 1存饮料右

     结点2 * n + 2 * f + 2 * d为s，t = s = 1。

 */

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + , maxm =  *  + , inf = 0x3f3f3f3f;

 int numf[maxn], numd[maxn];

 char str[maxn];

 int tot, head[maxn << ], que[maxn << ], dep[maxn << ], cur[maxn << ], sta[maxn << ];

 struct Edge {

     int to, cap, flow, next, from;

 } edge[maxm << ];

 void init() {

     tot = ;

     memset(head, -, sizeof head);

 }

 void addedge(int u, int v, int w) {

     edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = ; edge[tot].from = u;

     edge[tot].next = head[u]; head[u] = tot ++;

     edge[tot].to = u; edge[tot].cap = ; edge[tot].flow = ; edge[tot].from = v;

     edge[tot].next = head[v]; head[v] = tot ++;

 }

 bool bfs(int s, int t, int n) {

     memset(dep, -, sizeof dep[] * (n + ));

     int front = , tail = ;

     dep[s] = ;

     que[tail ++] = s;

     while(front < tail) {

         int u = que[front ++];

         for(int i = head[u]; ~i; i = edge[i].next) {

             int v = edge[i].to;

             if(edge[i].cap > edge[i].flow && dep[v] == -) {

                 dep[v] = dep[u] + ;

                 if(v == t) return true;

                 que[tail ++] = v;

             }

         }

     }

     return false;

 }

 int dinic(int s, int t, int n) {

     int maxflow = ;

     while(bfs(s, t, n)) {

         for(int i = ; i <= n; i ++) cur[i] = head[i];

         int u = s, tail = ;

         while(~cur[s]) {

             if(u == t) {

                 int tp = inf;

                 for(int i = tail - ; i >= ; i --)

                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);

                 maxflow += tp;

                 for(int i = tail - ; i >= ; i --) {

                     edge[sta[i]].flow += tp;

                     edge[sta[i] ^ ].flow -= tp;

                     if(edge[sta[i]].cap - edge[sta[i]].flow == )   tail = i;

                 }

                 u = edge[sta[tail] ^ ].to;

             } else if(~ cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] +  == dep[edge[cur[u]].to]) {

                 sta[tail ++] = cur[u];

                 u = edge[cur[u]].to;

             } else {

                 while(u != s && cur[u] == -)

                     u = edge[sta[-- tail] ^ ].to;

                 cur[u] = edge[cur[u]].next;

             }

         }

     }

     return maxflow;

 }

 int main() {

     int n, f, d;

     while(~scanf("%d %d %d", &n, &f, &d)) {

         init();

         int s =  * n +  * f + d * , t = s + ;//超级源点和超级汇点

         for(int i = ; i < f; i ++) {

             scanf("%d", &numf[i]);

             addedge(s,  * n + i, inf);//超级源点到食物左

             addedge( * n + i,  * n + f + i, numf[i]);//食物左到食物右

         }

         for(int i = ; i < d; i ++) {

             scanf("%d", &numd[i]);

             addedge( * n +  * f + i,  * n +  * f + d + i, numd[i]);//饮料左到饮料右

             addedge( * n +  * f + d + i, t, inf);//饮料右到超级汇点

         }

         for(int i = ; i < n; i ++) {

             addedge(i, n + i, );//左牛到右牛

         }

         for(int i = ; i < n; i++) {

             scanf("%s", str);

             for(int j = ; j < f; j ++) {

                 if(str[j] == 'Y')

                     addedge( * n + f + j, i, );//从食物右到左牛

             }

         }

         for(int i = ; i < n; i ++) {

             scanf("%s", str);

             for(int j = ; j < d; j ++) {

                 if(str[j] == 'Y')

                     addedge(n + i,  * n +  * f + j, );//从右牛到左饮料

             }

         }

         // for(int i = 2; i <= tot; i ++) {

         //     printf("%d -> %d\n", edge[i].from, edge[i].to);

         // }

         printf("%d\n", dinic(s, t,  * n +  * f +  * d + ));

     }

     return ;

 }

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

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + , maxm =  *  + , inf = 0x3f3f3f3f;

 int numf[maxn], numd[maxn];

 char str[maxn];

 int tot, head[maxn << ], que[maxn << ], dep[maxn << ], cur[maxn << ], sta[maxn << ];

 struct Edge {

     int to, cap, flow, next, from;

 } edge[maxm << ];

 void init() {

     tot = ;

     memset(head, -, sizeof head);

 }

 void addedge(int u, int v, int w) {

     edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = ; edge[tot].from = u;

     edge[tot].next = head[u]; head[u] = tot ++;

     edge[tot].to = u; edge[tot].cap = ; edge[tot].flow = ; edge[tot].from = v;

     edge[tot].next = head[v]; head[v] = tot ++;

 }

 bool bfs(int s, int t, int n) {

     memset(dep, -, sizeof dep[] * (n + ));

     int front = , tail = ;

     dep[s] = ;

     que[tail ++] = s;

     while(front < tail) {

         int u = que[front ++];

         for(int i = head[u]; ~i; i = edge[i].next) {

             int v = edge[i].to;

             if(edge[i].cap > edge[i].flow && dep[v] == -) {

                 dep[v] = dep[u] + ;

                 if(v == t) return true;

                 que[tail ++] = v;

             }

         }

     }

     return false;

 }

 int dinic(int s, int t, int n) {

     int maxflow = ;

     while(bfs(s, t, n)) {

         for(int i = ; i <= n; i ++) cur[i] = head[i];

         int u = s, tail = ;

         while(~cur[s]) {

             if(u == t) {

                 int tp = inf;

                 for(int i = tail - ; i >= ; i --)

                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);

                 maxflow += tp;

                 for(int i = tail - ; i >= ; i --) {

                     edge[sta[i]].flow += tp;

                     edge[sta[i] ^ ].flow -= tp;

                     if(edge[sta[i]].cap - edge[sta[i]].flow == )   tail = i;

                 }

                 u = edge[sta[tail] ^ ].to;

             } else if(~ cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] +  == dep[edge[cur[u]].to]) {

                 sta[tail ++] = cur[u];

                 u = edge[cur[u]].to;

             } else {

                 while(u != s && cur[u] == -)

                     u = edge[sta[-- tail] ^ ].to;

                 cur[u] = edge[cur[u]].next;

             }

         }

     }

     return maxflow;

 }

 int main() {

     int n, f, d;

     while(~scanf("%d %d %d", &n, &f, &d)) {

         init();

         int s =  * n + f + d, t = s + ;//超级源点和超级汇点

         for(int i = ; i < f; i ++) {

             scanf("%d", &numf[i]);

             addedge(s, n *  + i, numf[i]);

         }

         for(int i = ; i < d; i ++) {

             scanf("%d", &numd[i]);

             addedge(n *  + f + i, t, numd[i]);

         }

         for(int i = ; i < n; i++) {

             addedge(i, n + i, );//左牛到右牛

             scanf("%s", str);

             for(int j = ; j < f; j ++) {

                 if(str[j] == 'Y')

                     addedge( * n + j, i, );

             }

         }

         for(int i = ; i < n; i ++) {

             scanf("%s", str);

             for(int j = ; j < d; j ++) {

                 if(str[j] == 'Y')

                     addedge(n + i,  * n + f + j, );//从右牛到饮料

             }

         }

         // for(int i = 2; i <= tot; i ++) {

         //     printf("%d -> %d\n", edge[i].from, edge[i].to);

         // }

         printf("%d\n", dinic(s, t,  * n + f + d + ));

     }

     return ;

 }

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

巴特西

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

Food

最新文章

热门文章