HDU 4292 网络源 Food

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 536870912

inline 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 3
1 1 1
1 1 1
YYN
NYY
YNY
YNY
YNY
YYN
YYN
NNY

2 1 1
10
10
Y
N
Y
N

2 1 2 
10 
1 2
Y
Y
YN
NN


*/