/*
题意:每一个人都有喜欢的吃的和喝的,每一个人只选择一个数量的吃的和一个数量的喝的,问能满足最多的人数!?
思路:建图很是重要!f-food, p-people, d-drink
建图: 0(源点)--->f--->p---->p'---->d--->t(汇点)
将人拆分很是重要,因为每一个人最多只能有一种选择,也就是p--->p'的最大流量是 1!
如果还是不清楚,看一看下图的例子,将人拆分与不拆分的区别!
*/
1 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define N 850
#define M 201000
#define INF 0x3f3f3f3f
using namespace std;
struct EDGE{
int v, cap, nt;
};
int first[N];
EDGE g[M];
int cnt;
int n, f, d;
void addEdge(int u, int v, int cap){
g[cnt].v=v;
g[cnt].cap=cap;
g[cnt].nt=first[u];
first[u]=cnt++;
g[cnt].v=u;
g[cnt].cap=;
g[cnt].nt=first[v];
first[v]=cnt++;
}
int ans, ss;
queue<int>q;
int dist[N];
bool bfs(){
memset(dist, , sizeof(dist));
dist[]=;
q.push();
while(!q.empty()){
int u=q.front();
q.pop();
for(int e=first[u]; ~e; e=g[e].nt){
int v=g[e].v;
int cap=g[e].cap;
if(!dist[v] && cap>){
dist[v]=dist[u]+;
q.push(v);
}
}
}
if(dist[ss+]==) return false;
return true;
}
int dfs(int u, int flow){
int ff;
if(u==ss+) return flow;
for(int e=first[u]; ~e; e=g[e].nt){
int v=g[e].v;
int cap=g[e].cap;
if(dist[v]==dist[u]+ && cap> && (ff=dfs(v, min(cap, flow)))){
g[e].cap-=ff;
g[e^].cap+=ff;
return ff;
}
}
dist[u]=-;//表示u节点不能到达汇点!
return ;
}
void Dinic(){
ans=;
int d;
while(bfs())
while(d=dfs(, INF))
ans+=d;
}
int main(){
while(scanf("%d%d%d", &n, &f, &d)!=EOF){
ss=*n+f+d;
cnt=;
memset(first, -, sizeof(first));
for(int i=; i<=f; ++i){//源点到吃的建一条有向边,最大流量为吃的的数量
int x;
scanf("%d", &x);
addEdge(, i, x);
}
for(int i=; i<=d; ++i){//喝的到汇点建一条有向边,最大流量为喝的的数量
int x;
scanf("%d", &x);
addEdge(n*+f+i, ss+, x);
}
for(int i=; i<=n; ++i){//吃的到人建一条有向边,最大流量为1
getchar();
for(int j=; j<=f; ++j){
char ch;
scanf("%c", &ch);
if(ch=='Y')
addEdge(j, f+i, );
}
}
for(int i=; i<=n; ++i){//人到喝的建一条有向边,最大流量为1
addEdge(f+i, n+f+i, );//人属于节点容量,将人进行拆分,因为每一个人只能有一种选择!
getchar();
for(int j=; j<=d; ++j){
char ch;
scanf("%c", &ch);
if(ch=='Y')
addEdge(n+f+i, f+n*+j, );
}
}
Dinic();
printf("%d\n", ans);
}
return ;
}