题目大意：有n个人，f的food，d的饮料，每个人对事物和饮料有偏好，并且如果一个人没有饮料或者事物他就会离开，问最后最多有几个人留下来；
题目解析：开始是超级食物汇点，中间是人，因为每个人最多选一种食物，所以人与自己也要加一条边，最后是超级饮料汇点，最大流EK即可；
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> using namespace std; const int inf=0x3fffffff; const int maxn=10010; struct node { int to,cap,rev; node(int a,int b,int c) { to=a; cap=b; rev=c; } }; vector<node>vec[maxn]; int pre[maxn],iter[maxn]; void add_edge(int from,int to,int cost) { vec[from].push_back(node(to,cost,vec[to].size())); vec[to].push_back(node(from,0,vec[from].size()-1)); } void bfs(int s){ memset(pre,-1,sizeof(pre)); queue<int>que; pre[s]=0;que.push(s); while(!que.empty()){ int v=que.front();que.pop(); for(int i=0;i<vec[v].size();i++){ node &e=vec[v][i]; if(e.cap>0&&pre[e.to]<0){ pre[e.to]=pre[v]+1; que.push(e.to); } } } } int dfs(int v,int t,int f){ if(v==t) return f; for(int &i=iter[v];i<vec[v].size();i++){ node &e=vec[v][i]; if(e.cap>0&&pre[v]<pre[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; vec[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int u,int v) { int flow=0; while(1) { bfs(u); if(pre[v]<0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(u,v,inf))>0) flow+=f; } } int main() { int n,i,j,f,d,t; char str[1001]; while(scanf("%d%d%d",&n,&f,&d)!=EOF) { for(i=0;i<maxn;i++) vec[i].clear(); for(i=1;i<=f;i++) { scanf("%d",&t); add_edge(0,i,t); } for(i=1;i<=d;i++) { scanf("%d",&t); add_edge(n+n+f+i,n+n+f+d+1,t); } for(i=1;i<=n;i++) { add_edge(f+i,f+i+n,1); } for(i=1;i<=n;i++) { scanf("%s",&str[0]); for(j=0;j<f;j++) { if(str[j]=='Y') add_edge(j+1,f+i,1); } } for(i=1;i<=n;i++) { scanf("%s",&str[0]); for(j=0;j<d;j++) { if(str[j]=='Y') add_edge(n+f+i,2*n+f+j+1,1); } } int ans=max_flow(0,n+n+f+d+1); printf("%d\n",ans); } return 0; }
