HDU 4292 网络流 Food
题意：
n 个人 f 种食物 d 种饮料
f 个数字表示每种食物的个数
d个数字表示每种饮料的个数
n行f列
i行j列表示 第i个人是否喜欢 第j 种食物
n行d列
同上
当一个人同时有吃有喝就被满足，问最多能满足多少人
思路：
设0为源点
[1, f ] 表示食物 （若i行j列是 Y 则建边 addedge(i, f+j , 1) ）
把人拆点拆成 i 和 i+n 边权为1
[f +1, f + n] 和 [ f + n +1, f + n +n ] 表示人
[ f+n+n +i, f+n+n + d]表示各种饮料，与 人建边如上
再把饮料连到汇点
则最大流就是最大人数
#include <stdio.h>#include <string.h>#include <queue>using namespace std;#define N 90000#define inf 536870912inline int Max(int a,int b){return a<b?b:a;}inline int Min(int a,int b){return a>b?b:a;}struct Edge{int from, to, cap, nex;}edge[N*10];int head[N], edgenum;void addedge(int u, int v, int cap){Edge E = { u, v, cap, head[u]};edge[ edgenum ] = E;head[u] = edgenum ++;Edge E1= { v, u, 0, head[v]};edge[ edgenum ] = E1;head[v] = edgenum ++;}int sign[N], s, t;bool BFS(int from, int to){memset(sign, -1, sizeof(sign));sign[from] = 0;queue<int>q;q.push(from);while( !q.empty() ){int u = q.front(); q.pop();for(int i = head[u]; i!=-1; i = edge[i].nex){int v = edge[i].to;if(sign[v]==-1 && edge[i].cap){sign[v] = sign[u] + 1, q.push(v);if(sign[to] != -1)return true;}}}return false;}int Stack[N], top, cur[N];int dinic(){int ans = 0;while( BFS(s, t) ){memcpy(cur, head, sizeof(head));int u = s;top = 0;while(1){if(u == t){int flow = inf, loc;//loc 表示 Stack 中 cap 最小的边for(int i = 0; i < top; i++)if(flow > edge[ Stack[i] ].cap){flow = edge[Stack[i]].cap;loc = i;}for(int i = 0; i < top; i++){edge[ Stack[i] ].cap -= flow;edge[Stack[i]^1].cap += flow;}ans += flow;top = loc;u = edge[Stack[top]].from;}for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;if(cur[u] != -1){Stack[top++] = cur[u];u = edge[ cur[u] ].to;}else{if( top == 0 )break;sign[u] = -1;u = edge[ Stack[--top] ].from;}}}return ans;}int flow;char hehe[300];int main(){int n,f,d;int i, j;while(~scanf("%d %d %d",&n,&f,&d)){memset(head,-1,sizeof(head)); edgenum = 0;s = 0, t = f + 2*n + d + 1;for(i = 1;i <= f; i++){scanf("%d",&flow);addedge(s, i, flow);}for(i = 1;i <= d; i++){scanf("%d",&flow);addedge(f+2*n+i, t, flow);}for(i = 1;i <= n; i++){scanf("%s",hehe+1);for(j = 1; j <= f; j++)if(hehe[j] == 'Y'){addedge(j, f+i, 1);}}for(i = 1;i <= n; i++){scanf("%s",hehe+1);for(j = 1; j <= d; j++)if(hehe[j] == 'Y'){addedge(f+n+i, f+2*n+j, 1);}}for(i = 1;i <= n; i++)addedge(f+i, f+n+i, 1);printf("%d\n",dinic());}return 0;}/*4 3 31 1 11 1 1YYNNYYYNYYNYYNYYYNYYNNNY2 1 11010YNYN2 1 2 10 1 2YYYNNN*/