)
Food/* Food HDU - 4292 https://cn.vjudge.net/problem/HDU-4292 题面每个人有多个喜欢的食物和饮料每个人只能挑一种食物和饮料问最大能满足多少人 解法 割点吧人分成两部分中间用边权为1的线连接这样保证每个人只能挑一种食物和饮料 建图原点--食物--人1--人2--饮料--汇点 开始跑最大流 */#includecstdio#includecstring#includealgorithm#includequeue#includeiostreamusing namespace std;#defineINF 0x3f3f3f3f#definemaxn 1001000#definell long longstructnode{intv,w;intnext;}wedge[maxn1];intwhead[maxn];intwcnt;intdis[maxn];intn,f,d;intfx,dx;intB,E;voidinit(){memset(whead,-1,sizeofwhead);wcnt0;}voidadd(intu,intv,intw){wedge[wcnt].ww;wedge[wcnt].vv;wedge[wcnt].nextwhead[u];whead[u]wcnt;wedge[wcnt].w0;wedge[wcnt].vu;wedge[wcnt].nextwhead[v];whead[v]wcnt;}boolbfs(intB,intE){memset(dis,-1,sizeofdis);queueintq;dis[B]0;q.push(B);while(!q.empty()){intstq.front();q.pop();for(intiwhead[st];~i;iwedge[i].next){if(dis[wedge[i].v]-1wedge[i].w0){dis[wedge[i].v]dis[st]1;q.push(wedge[i].v);}}}returndis[E]!-1;}intdfs(intu,intlow){intflow;if(uE)returnlow;for(intiwhead[u];i!-1;iwedge[i].next){if(wedge[i].w(dis[wedge[i].v]dis[u]1)(flowdfs(wedge[i].v,min(low,wedge[i].w)))){wedge[i].w-flow;wedge[i^1].wflow;returnflow;}}dis[u]-1;return0;}voiddinic(intB,intE){intans0;intt;while(bfs(B,E)){while(tdfs(B,INF))anst;}printf(%d\n,ans);}intmain(){while(~scanf(%d %d %d,n,f,d)){init();B0,E8001;for(inti1;if;i){scanf(%d,fx);add(0,i,fx);}for(inti1;id;i){scanf(%d,dx);add(600i,E,dx);}charc[300];for(inti1;in;i){scanf(%s,c1);for(intj1;jf;j){if(c[j]Y){add(j,200i,1);}}}for(inti1;in;i){scanf(%s,c1);for(intj1;jd;j){if(c[j]Y){add(400i,600j,1);}}}for(inti1;in;i){add(i200,i2*200,1);}dinic(B,E);}}
