Food

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2136 Accepted Submission(s): 745

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

YYN

NYY

YNY

YYN

NNY

Sample Output

Source

构图是老生常谈的事情了。

S-->food连边food[i] ;

food-->man1连边1

man1-->man2连边1

mam2-->drink 连边1 ，

diink-->T连边dink[i]

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std ;typedef long long LL ;#define MAXN 1000#define inf 2100000000int g[MAXN][MAXN],level[MAXN];int bfs(int n,int s,int t){ int que[1000],head,tail,i; head=tail=0; que[tail++]=s; memset(level,-1,sizeof(level)); level[s]=1; while(head
                  
                   g[path[i]][path[i+1]]){ low=g[path[i]][path[i+1]]; cut=i; } } maxflow+=low; for(i=0;i

转载于:https://www.cnblogs.com/liyangtianmen/p/3379707.html

你可能感兴趣的文章