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 31 1 11 1 1YYNNYYYNYYNYYNYYYNYYNNNY

Sample Output

3

 

 

题意：

有一些个数有限的  不同种类的糖果 和 一些不同种类的饮料 ， 每个人的口味不同，所以可以选择任意的糖果和饮料 ， 每个都只选一个 

 求能满足最多的人的数量

 

解析：

建立超级源点s和超级汇点t  把s和糖果连在一起，边权为糖果的数量，  t和饮料连载一其，边权为饮料的数量， 然后把每一个人拆成两个点 其中边权为1

人和糖果、饮料 都建立边 边权为INF；

代码如下：

Dinic + 当前弧优化 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn =101000, INF = 0x7fffffff;int cnt = 0, s, t;int head[maxn], d[maxn], cur[maxn];char str[300];struct node{    int u, v, c, next;}Node[maxn*4];void add_(int u, int v, int c){    Node[cnt].u = u;    Node[cnt].v = v;    Node[cnt].c = c;    Node[cnt].next = head[u];    head[u] = cnt++;}void add(int u,int v,int c){    add_(u,v,c);    add_(v,u,0);}bool bfs(){    queue
          
            Q; mem(d,0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u]; i!=-1; i=Node[i].next) { node e = Node[i]; if(!d[e.v] && e.c > 0) { d[e.v] = d[e.u] + 1; // cout<< e.v << " " << d[e.v] <
           
             0) { int V = dfs(e.v, min(cap, e.c)); Node[i].c -= V; Node[i^1].c += V; cap -= V; ret += V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret;}int Dinic(){ int ans = 0; while(bfs()) { memcpy(cur,head,sizeof(head)); ans += dfs(s,INF); } return ans;}int main(){ int n, f, d; while(~scanf("%d%d%d",&n,&f,&d)) { cnt = 0; mem(head,-1); int temp; s = 0, t = f+d+n+n+10; for(int i=1; i<=f; i++) { scanf("%d",&temp); add(s,i,temp); } for(int i=1; i<=d; i++) { scanf("%d",&temp); add(f+i,t,temp); } for(int i=1; i<=n; i++) { scanf("%s",str); for(int j=0; j