pigs(最大流，建图需要思考).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MMAX 1100
#define NMAX 110

int net[NMAX+MMAX][NMAX+MMAX];
int n,m;
int path[NMAX+MMAX];
int precus[NMAX];

int bfs()
{
	int now, i, neck;
	queue<int> SQ;
	SQ.push(0);
	memset(path,-1,sizeof(path));
	path[0] = 0;

	while(!SQ.empty()) {
		now = SQ.front();
		SQ.pop();
		if(now == n) {
			break;
		}
		for(i=0;i<=n;i++) {
			if(path[i] == -1 && net[now][i] > 0) {
				SQ.push(i);
				path[i] = now;
			}
		}
	}
	if(path[n] == -1) {
		return -1;
	}
	now = n;
	neck = INT_MAX;
	while(now != 0) {
		int pre = path[now];
		neck = min(neck, net[pre][now]);
		now = pre;
	}
	return neck;
}

int Ford_Fulkerson()
{
	int i,j,step;
	int maxflow = 0;
	while( (step = bfs()) != -1) {
		maxflow += step;
		j = n;
		while(j != 0) {
			i = path[j];
			net[i][j] -= step;
			net[j][i] += step;
			j = i;
		}
	}
	return maxflow;
}

int main()
{
	int i,j,v;
	while(scanf("%d %d", &m,&n)==2) {
		memset(net,0,sizeof(net));
		memset(precus,-1,sizeof(precus));
		for(i=0;i<m;i++) {
			scanf("%d", &v);
			//s -> 猪圈，权为猪的数量
			net[0][i+1] = v;
		}
		for(i=0;i<n;i++) {
			int t;
			scanf("%d", &t);
			for(j=0;j<t;j++) {
				int key;
				scanf("%d", &key);
				//猪圈 -> 买主
				net[key][i+m+1] = INT_MAX;
				//前买主 -> 现买主（两者必须钥匙集合不为空）
				//因为猪可以从前买主能开的猪圈里调度过来
				if(precus[key] != -1) {
					net[m+1+ precus[key]][m+1+ i] = INT_MAX;
				}
				precus[key] = i;
			}
			scanf("%d", &t);
			//买主 -> t，权为最大购买量
			net[i+m+1][n+m+1] = t;
		}
		n += m+1;
		printf("%d\n", Ford_Fulkerson());
	}
}