HDU4292:Food(最大流)

Food

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

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4292

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:

题解：

详情可看这道题：https://www.cnblogs.com/heyuhhh/p/10085472.html

几乎一模一样...

直接上代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define t 1000
#define INF 99999999
using namespace std;
typedef long long ll;
const int N = 1005;
int n,F,D,tot;
int head[N],d[N];
struct Edge{
    int v,next,c;
}e[(N*N)<<1];
void adde(int u,int v,int c){
    e[tot].v=v;e[tot].c=c;e[tot].next=head[u];head[u]=tot++;
    e[tot].v=u;e[tot].c=0;e[tot].next=head[v];head[v]=tot++;
}
bool bfs(int S,int T){
    memset(d,0,sizeof(d));d[S]=1;
    queue <int > q;q.push(S);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(!d[v] && e[i].c>0){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[t]!=0;
}
int dfs(int s,int a){
    int flow=0,f;
    if(s==t || a==0) return a;
    for(int i=head[s];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(d[v]!=d[s]+1) continue ;
        f=dfs(v,min(a,e[i].c));
        if(f){
            e[i].c-=f;
            e[i^1].c+=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    if(!flow) d[s]=-1;
    return flow;
}
int Dinic(){
    int max_flow=0;
    while(bfs(0,t))
        max_flow+=dfs(0,INF);
    return max_flow;
}
int main(){
    while(~scanf("%d%d%d",&n,&F,&D)){
        tot=0;memset(head,-1,sizeof(head));
        for(int i=1,c;i<=F;i++){
            scanf("%d",&c);
            adde(0,i,c);
        }
        for(int i=1,c;i<=D;i++){
            scanf("%d",&c);
            adde(600+i,t,c);
        }
        for(int i=201;i<=400;i++) adde(i,i+200,1);
        char s[300];
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            for(int j=0;j<F;j++){
                if(s[j]=='Y') adde(j+1,i+200,1);
            }
        }
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            for(int j=0;j<D;j++){
                if(s[j]=='Y') adde(400+i,600+j+1,1);
            }
        }
        printf("%d
",Dinic());
    }
    return 0;
}

HDU4292:Food(最大流)

相关推荐