/*
  　　  题意：每一个人都有喜欢的吃的和喝的，每一个人只选择一个数量的吃的和一个数量的喝的，问能满足最多的人数！？
　　　　思路：建图很是重要！f-food, p-people, d-drink
　　　　建图：  0（源点）--->f--->p---->p‘---->d--->t(汇点)
　　　         将人拆分很是重要，因为每一个人最多只能有一种选择，也就是p--->p‘的最大流量是 1！
　　　　　　　　如果还是不清楚，看一看下图的例子，将人拆分与不拆分的区别！
　　　　　　　                 　
  */
  1 #include<iostream>  2 #include<cstring>  3 #include<cstdio>  4 #include<algorithm>  5 #include<vector>  6 #include<queue>  7 #define N 850  8 #define M 201000  9 #define INF 0x3f3f3f3f 10 using namespace std; 11  12 struct EDGE{ 13     int v, cap, nt; 14 }; 15  16 int first[N]; 17 EDGE g[M]; 18 int cnt; 19 int n, f, d; 20  21 void addEdge(int u, int v, int cap){ 22     g[cnt].v=v; 23     g[cnt].cap=cap; 24     g[cnt].nt=first[u]; 25     first[u]=cnt++; 26      27     g[cnt].v=u; 28     g[cnt].cap=0; 29     g[cnt].nt=first[v]; 30     first[v]=cnt++; 31 } 32  33 int ans, ss; 34  35 queue<int>q; 36 int dist[N]; 37  38 bool bfs(){ 39     memset(dist, 0, sizeof(dist)); 40     dist[0]=1; 41     q.push(0); 42     while(!q.empty()){ 43           int u=q.front(); 44         q.pop(); 45         for(int e=first[u]; ~e; e=g[e].nt){ 46                int v=g[e].v; 47             int cap=g[e].cap; 48             if(!dist[v] && cap>0){ 49                 dist[v]=dist[u]+1; 50                 q.push(v); 51             } 52         }     53     } 54     if(dist[ss+1]==0) return false; 55     return true; 56 } 57  58 int dfs(int u, int flow){ 59     int ff; 60     if(u==ss+1) return flow; 61     for(int e=first[u]; ~e; e=g[e].nt){ 62         int v=g[e].v; 63         int cap=g[e].cap;     64         if(dist[v]==dist[u]+1 && cap>0 && (ff=dfs(v, min(cap, flow)))){ 65             g[e].cap-=ff; 66             g[e^1].cap+=ff; 67             return ff; 68         } 69      } 70     dist[u]=-1;//表示u节点不能到达汇点！  71     return 0; 72 } 73  74 void Dinic(){ 75     ans=0; 76     int d; 77     while(bfs()) 78          while(d=dfs(0, INF)) 79             ans+=d; 80 } 81  82 int main(){ 83     while(scanf("%d%d%d", &n, &f, &d)!=EOF){ 84         ss=2*n+f+d; 85         cnt=0; 86         memset(first, -1, sizeof(first)); 87         for(int i=1; i<=f; ++i){//源点到吃的建一条有向边，最大流量为吃的的数量  88             int x; 89             scanf("%d", &x); 90             addEdge(0, i, x); 91         } 92  93         for(int i=1; i<=d; ++i){//喝的到汇点建一条有向边，最大流量为喝的的数量 94             int x; 95             scanf("%d", &x); 96             addEdge(n*2+f+i, ss+1, x); 97         } 98         for(int i=1; i<=n; ++i){//吃的到人建一条有向边，最大流量为1  99             getchar();100             for(int j=1; j<=f; ++j){101                 char ch;102                 scanf("%c", &ch);103                 if(ch==‘Y‘)104                     addEdge(j, f+i, 1);105             }106         }107 108         for(int i=1; i<=n; ++i){//人到喝的建一条有向边，最大流量为1 109             addEdge(f+i, n+f+i, 1);//人属于节点容量，将人进行拆分，因为每一个人只能有一种选择！ 110             getchar();111             for(int j=1; j<=d; ++j){112                 char ch;113                 scanf("%c", &ch);114                 if(ch==‘Y‘)115                     addEdge(n+f+i, f+n*2+j, 1);116             }117         }118 119         Dinic();120         printf("%d\n", ans);121     }122     return 0;123 }