Food

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

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

Recommend

liuyiding

题解：

此题（POJ3281 Dining）的变形，只不过是把超级汇点连向食物的边改为库存，饮料连向超级汇点的边改为库存。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cmath>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 const int INF = 2e9;
 15 const LL LNF = 9e18;
 16 const int mod = 1e9+7;
 17 const int MAXN = 1e3+10;
 18 
 19 int maze[MAXN][MAXN];
 20 int gap[MAXN], dis[MAXN], pre[MAXN], cur[MAXN];
 21 int flow[MAXN][MAXN];
 22 
 23 int sap(int start, int end, int nodenum)
 24 {
 25     memset(cur, 0, sizeof(cur));
 26     memset(dis, 0, sizeof(dis));
 27     memset(gap, 0, sizeof(gap));
 28     memset(flow, 0, sizeof(flow));
 29     int u = pre[start] = start, maxflow = 0, aug = INF;
 30     gap[0] = nodenum;
 31 
 32     while(dis[start]<nodenum)
 33     {
 34         loop:
 35         for(int v = cur[u]; v<nodenum; v++)
 36         if(maze[u][v]-flow[u][v]>0 && dis[u] == dis[v]+1)
 37         {
 38             aug = min(aug, maze[u][v]-flow[u][v]);
 39             pre[v] = u;
 40             u = cur[u] = v;
 41             if(v==end)
 42             {
 43                 maxflow += aug;
 44                 for(u = pre[u]; v!=start; v = u, u = pre[u])
 45                 {
 46                     flow[u][v] += aug;
 47                     flow[v][u] -= aug;
 48                 }
 49                 aug = INF;
 50             }
 51             goto loop;
 52         }
 53 
 54         int mindis = nodenum-1;
 55         for(int v = 0; v<nodenum; v++)
 56             if(maze[u][v]-flow[u][v]>0 && mindis>dis[v])
 57             {
 58                 cur[u] = v;
 59                 mindis = dis[v];
 60             }
 61         if((--gap[dis[u]])==0) break;
 62         gap[dis[u]=mindis+1]++;
 63         u = pre[u];
 64     }
 65     return maxflow;
 66 }
 67 
 68 char str[MAXN];
 69 int main()
 70 {
 71     int N, F, D;
 72     while(scanf("%d%d%d",&N,&F,&D)!=EOF)
 73     {
 74         int start = 0, end = F+D+2*N+1;
 75         memset(maze, 0, sizeof(maze));
 76         for(int i = 1; i<=F; i++)
 77         {
 78             int Food_supply;
 79             scanf("%d", &Food_supply);
 80             maze[start][i] = Food_supply;
 81         }
 82         for(int i = 1; i<=D; i++)
 83         {
 84             int Drink_supply;
 85             scanf("%d", &Drink_supply);
 86             maze[F+i][end] = Drink_supply;
 87         }
 88         for(int i = 1; i<=N; i++)
 89         {
 90             scanf("%s", str+1);
 91             for(int j = 1; j<=F; j++)
 92                 if(str[j]=='Y')
 93                     maze[j][F+D+i] = 1;
 94         }
 95         for(int i = 1; i<=N; i++)
 96         {
 97             scanf("%s", str+1);
 98             for(int j = 1; j<=D; j++)
 99                 if(str[j]=='Y')
100                     maze[F+D+N+i][F+j] = 1;
101         }
102         for(int i = 1; i<=N; i++)
103             maze[F+D+i][F+D+N+i] = 1;
104 
105         cout<< sap(start, end, F+D+2*N+2) <<endl;
106     }
107 }

View Code