HDU 4292 Food （网络流，最大流）

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

Http

HDU:https://vjudge.net/problem/HDU-4292

Hit

网络流，最大流

题目大意

现在提供若干种饮料、食物，每种都有一定的数量。给定N个人对每一种食物和饮料的喜好，若给某人提供了其喜欢的食物和饮料，则称这个人是开心的。现在求能使最多的人开心的数量。

解决思路

我们按照源点-食物-人-饮料-汇点的顺序建图。对于每一个食物，从源点连容量为其数量的的边，而对于每一个人，连接他和他所有喜欢的食物，容量都是1,。因为给一个人只提供一份食物和一份饮料，所以我们把人拆点，中间连容量为1的边。而对于饮料则是类似的，从人到他喜欢的饮料连容量为1的边，从饮料到汇点连容量为其数量的边。这样跑最大流即可。 关于最大流，这里使用Dinic，可以参考这篇文章

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int maxN=1001; const int maxM=maxN*maxN*2; const int inf=2147483647; class Edge { public: int u,v,flow; }; int N,F,D;//点的编号安排：0汇点，[1,N]人1，[N+1,N*2]人2，[N*2+1,N*2+F]食物，[N*2+F+1,N*2+F+D]饮料，N*2+F+D+1汇点 int cnt=-1; char str[maxN]; int Head[maxN]; int Next[maxM]; Edge E[maxM]; int depth[maxN]; int cur[maxN]; int Q[maxN]; void Add_Edge(int u,int v,int flow); bool bfs(); int dfs(int u,int flow); int main() { while (cin>>N>>F>>D)//多组数据 { cnt=-1;//先清空 memset(Head,-1,sizeof(Head)); for (int i=1;i<=F;i++)//读入食物的数量 { int maxflow; scanf("%d",&maxflow); Add_Edge(0,N*2+i,maxflow);//连接源点和食物 } for (int i=1;i<=D;i++)//读入饮料的数量 { int maxflow; scanf("%d",&maxflow); Add_Edge(N*2+F+i,N*2+F+D+1,maxflow);//连接饮料和汇点 } for (int i=1;i<=N;i++) { scanf("%s",str); for (int j=0;j<F;j++) if (str[j]=='Y') Add_Edge(N*2+j+1,i,1);//连接人与食物 } for (int i=1;i<=N;i++) { scanf("%s",str); for (int j=0;j<D;j++) if (str[j]=='Y') Add_Edge(N+i,N*2+F+j+1,1);//连接人与饮料 } for (int i=1;i<=N;i++) Add_Edge(i,N+i,1);//连接人1与人2，即拆开的两个点 int Ans=0;//求解最大流 while (bfs()) { for (int i=0;i<=2*N+F+D+1;i++) cur[i]=Head[i]; while (int di=dfs(0,inf)) Ans+=di; } cout<<Ans<<endl; } return 0; } void Add_Edge(int u,int v,int flow) { cnt++; Next[cnt]=Head[u]; Head[u]=cnt; E[cnt].u=u; E[cnt].v=v; E[cnt].flow=flow; cnt++; Next[cnt]=Head[v]; Head[v]=cnt; E[cnt].u=v; E[cnt].v=u; E[cnt].flow=0; } bool bfs() { memset(depth,-1,sizeof(depth)); int h=1,t=0; depth[0]=1; Q[1]=0; do { t++; int u=Q[t]; for (int i=Head[u];i!=-1;i=Next[i]) { int v=E[i].v; if ((depth[v]==-1)&&(E[i].flow>0)) { depth[v]=depth[u]+1; h++; Q[h]=v; } } } while (t!=h); if (depth[N*2+F+D+1]==-1) return 0; return 1; } int dfs(int u,int flow) { if (u==N*2+F+D+1) return flow; for (int i=Head[u];i!=-1;i=Next[i]) { int v=E[i].v; if ((depth[v]==depth[u]+1)&&(E[i].flow>0)) { int di=dfs(v,min(flow,E[i].flow)); if (di>0) { E[i].flow-=di; E[i^1].flow+=di; return di; } } } return 0; }

转载于:https://www.cnblogs.com/SYCstudio/p/7380827.html