题目链接：https://vjudge.net/problem/HDU-4292

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）的变形，只不过是把超级汇点连向食物的边改为库存，饮料连向超级汇点的边改为库存。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int MAXN = 1e3+;

 int maze[MAXN][MAXN];

 int gap[MAXN], dis[MAXN], pre[MAXN], cur[MAXN];

 int flow[MAXN][MAXN];

 int sap(int start, int end, int nodenum)

 {

     memset(cur, , sizeof(cur));

     memset(dis, , sizeof(dis));

     memset(gap, , sizeof(gap));

     memset(flow, , sizeof(flow));

     int u = pre[start] = start, maxflow = , aug = INF;

     gap[] = nodenum;

     while(dis[start]<nodenum)

     {

         loop:

         for(int v = cur[u]; v<nodenum; v++)

         if(maze[u][v]-flow[u][v]> && dis[u] == dis[v]+)

         {

             aug = min(aug, maze[u][v]-flow[u][v]);

             pre[v] = u;

             u = cur[u] = v;

             if(v==end)

             {

                 maxflow += aug;

                 for(u = pre[u]; v!=start; v = u, u = pre[u])

                 {

                     flow[u][v] += aug;

                     flow[v][u] -= aug;

                 }

                 aug = INF;

             }

             goto loop;

         }

         int mindis = nodenum-;

         for(int v = ; v<nodenum; v++)

             if(maze[u][v]-flow[u][v]> && mindis>dis[v])

             {

                 cur[u] = v;

                 mindis = dis[v];

             }

         if((--gap[dis[u]])==) break;

         gap[dis[u]=mindis+]++;

         u = pre[u];

     }

     return maxflow;

 }

 char str[MAXN];

 int main()

 {

     int N, F, D;

     while(scanf("%d%d%d",&N,&F,&D)!=EOF)

     {

         int start = , end = F+D+*N+;

         memset(maze, , sizeof(maze));

         for(int i = ; i<=F; i++)

         {

             int Food_supply;

             scanf("%d", &Food_supply);

             maze[start][i] = Food_supply;

         }

         for(int i = ; i<=D; i++)

         {

             int Drink_supply;

             scanf("%d", &Drink_supply);

             maze[F+i][end] = Drink_supply;

         }

         for(int i = ; i<=N; i++)

         {

             scanf("%s", str+);

             for(int j = ; j<=F; j++)

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

                     maze[j][F+D+i] = ;

         }

         for(int i = ; i<=N; i++)

         {

             scanf("%s", str+);

             for(int j = ; j<=D; j++)

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

                     maze[F+D+N+i][F+j] = ;

         }

         for(int i = ; i<=N; i++)

             maze[F+D+i][F+D+N+i] = ;

         cout<< sap(start, end, F+D+*N+) <<endl;

     }

 }

巴特西

HDU4292 Food —— 最大流 + 拆点

Food

最新文章

热门文章