HDU 4292 Food 最大流-白红宇

HDU 4292 Food 最大流

阅读量：5227 次

发布时间：2019-06-14

本文共 4725 字，大约阅读时间需要 15 分钟。

H - Food

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88038#problem/H

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

YYN

NYY

YNY

YYN

NNY

Sample Output

HINT

题意

有n个人，f种食物，d种饮料

每个人对食物和饮料都有喜好，然后问你有多少个人既可以吃到食物，也可以喝到饮料

题解：

和养牛那道题差不多

s-食物-人-人-饮料-t

注意拆点，然后跑一发最大流就好了

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 5000#define mod 10007#define eps 1e-9int Num;//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//**************************************************************************************namespace NetFlow{ const int MAXN=100000,MAXM=1000000,inf=1e9; struct Edge { int v,c,f,nx; Edge() {} Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {} } E[MAXM]; int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz; void init(int _n) { N=_n,sz=0; memset(G,-1,sizeof(G[0])*N); } void link(int u,int v,int c) { E[sz]=Edge(v,c,0,G[u]); G[u]=sz++; E[sz]=Edge(u,0,0,G[v]); G[v]=sz++; } int ISAP(int S,int T) { //S -> T int maxflow=0,aug=inf,flag=false,u,v; for (int i=0;i
                   
                    E[it].f&&dis[u]==dis[v=E[it].v]+1) { if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f; pre[v]=u,u=v; flag=true; if (u==T) { for (maxflow+=aug;u!=S;) { E[cur[u=pre[u]]].f+=aug; E[cur[u]^1].f-=aug; } aug=inf; } break; } } if (flag) continue; int mx=N; for (int it=G[u];~it;it=E[it].nx) { if (E[it].c>E[it].f&&dis[E[it].v]
                    
                     E[it].f) { dis[v]=dis[u]+1; Q[t++]=v; } } } return dis[T]!=-1; } int dfs(int u,int T,int low) { if (u==T) return low; int ret=0,tmp,v; for (int &it=cur[u];~it&&ret
                     
                      E[it].f) { if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f))) { ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp; } } } if (!ret) dis[u]=-1; return ret; } int dinic(int S,int T) { int maxflow=0,tmp; while (bfs(S,T)) { memcpy(cur,G,sizeof(G[0])*N); while (tmp=dfs(S,T,inf)) maxflow+=tmp; } return maxflow; }}using namespace NetFlow;int A[300][5];int tot=1;int get_id(int x,int y){ if(A[x][y]==0) A[x][y]=tot++; return A[x][y];}int main(){ int n,f,d; while(scanf("%d%d%d",&n,&f,&d)!=EOF) { memset(A,0,sizeof(A)); tot=1; init(50000); for(int i=1;i<=f;i++) { int x=read(); link(get_id(1,0),get_id(i,2),x); } for(int i=1;i<=d;i++) { int x=read(); link(get_id(i,3),get_id(2,0),x); } for(int i=1;i<=n;i++) { link(get_id(i,1),get_id(i,4),1); } string s; for(int i=1;i<=n;i++) { cin>>s; for(int j=0;j
                      
                       >s; for(int j=0;j

转载于:https://www.cnblogs.com/qscqesze/p/4738175.html

你可能感兴趣的文章