据说也是原题，N个人,F种食物，D种饮料，每种食物和饮料都有一定的数量，而每个人都有自己喜欢的食物和饮料，当一个人拿到自己喜欢的食物之一以及喜欢的饮料之一时，这个人能够被满足。求最多能满足多少人。
看到题就觉得是网络流，但一时没想到怎么建图，斌牛一看题就说是原题，然后啪啪啪敲完键盘就过了。。
食物放左边，饮料放右边，人放在中间，拆成两个点，点间流量为一，然后左点连喜欢的食物，右点连喜欢的饮料，再加个源点和汇点，做一遍网络流就OK了。。
1 #include <string.h> 2 #include <stdio.h> 3 #include <algorithm> 4 #define MAXN 1000 5 #define MAXE 1000000 6 #define INF 0x3f3f3f3f 7 struct edge{ 8 int v,e,n,flow; 9 }e[MAXE]; 10 int first[MAXN],es; 11 int work[MAXN],q[MAXN],d[MAXN],front,rear; 12 void addedge(int u,int v,int flow){ 13 e[es].v=v,e[es].flow=flow,e[es].n=first[u],first[u]=es++; 14 } 15 int bfs(int s,int t,int n){ 16 memset(d,-1,sizeof(d[0])*(n+1)); 17 q[front=rear=d[s]=0]=s,rear++; 18 while(front<rear){ 19 int u=q[front++]; 20 for(int i=first[u];i!=-1;i=e[i].n) 21 if(e[i].flow&&d[e[i].v]==-1){ 22 d[e[i].v]=d[u]+1,q[rear++]=e[i].v; 23 if(e[i].v==t)return 1; 24 } 25 } 26 return 0; 27 } 28 int dfs(int cur,int t,int res){ 29 if(cur==t)return res; 30 for(int &i=work[cur];i!=-1;i=e[i].n) 31 if(e[i].flow&&d[e[i].v]==d[cur]+1) 32 if(int tmp=dfs(e[i].v,t,std::min(res,e[i].flow))){ 33 e[i].flow-=tmp,e[i^1].flow+=tmp; 34 return tmp; 35 } 36 return 0; 37 } 38 int dinic(int s,int t,int n){ 39 int ans=0,tt; 40 while(bfs(s,t,n)){ 41 memcpy(work,first,sizeof(first[0])*(n+1)); 42 while(tt=dfs(s,t,INF))ans+=tt; 43 } 44 return ans; 45 } 46 int n,ds,fs,ff[205],dd[205]; 47 char s[205]; 48 int main(){ 49 //freopen("test.in","r",stdin); 50 while(scanf("%d%d%d",&n,&fs,&ds)!=EOF){ 51 memset(first,-1,sizeof first);es=0; 52 for(int i=1;i<=n;i++){ 53 addedge(i<<1,i<<1|1,1); 54 addedge(i<<1|1,i<<1,0); 55 } 56 int bf=n*2+2,bd=bf+fs,ss=0,tt=bf; 57 for(int i=1;i<=fs;i++){ 58 scanf("%d",&ff[i]); 59 addedge(ss,bf+i,ff[i]); 60 addedge(bf+i,ss,0); 61 } 62 for(int i=1;i<=ds;i++){ 63 scanf("%d",&dd[i]); 64 addedge(bd+i,tt,dd[i]); 65 addedge(tt,bd+i,0); 66 } 67 for(int i=1;i<=n;i++){ 68 scanf("%s",s+1); 69 for(int j=1;j<=strlen(s+1);j++){ 70 if(s[j]=='Y'){ 71 addedge(bf+j,i<<1,INF); 72 addedge(i<<1,bf+j,0); 73 } 74 } 75 } 76 for(int i=1;i<=n;i++){ 77 scanf("%s",s+1); 78 for(int j=1;j<=strlen(s+1);j++){ 79 if(s[j]=='Y'){ 80 addedge(i<<1|1,bd+j,INF); 81 addedge(bd+j,i<<1|1,0); 82 } 83 } 84 } 85 printf("%d\n",dinic(ss,tt,bd+ds+1)); 86 } 87 88 return 0; 89 }