a plug for unix(ford_forlkerson).cpp

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

#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

const int NMAX = 510;

char plug[NMAX][30];
int num[NMAX];
int net[NMAX][NMAX];
int n,m,k;
int path[NMAX], neck[NMAX];

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

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

int Ford_Fulkerson()
{
	int max_flow = 0;
	int step, now;

	while((step=bfs()) != -1) {
		max_flow += step;
		now = n+1;
		while(now != 0) {
			int pre = path[now];
			net[pre][now] -= step;
			net[now][pre] += step;
			now = pre;
		}
	}
	return max_flow;
}

int find(char st[])
{
	int i;
	for(i=1;i<=n;i++) {
		if(strcmp(st, plug[i]) == 0) {
			return i;
		}
	}
	return -1;
}

int main()
{
	int i,j,tn,tm,t;
	char device[30], dplug[30], adap[30];

	while(scanf("%d", &n)==1) {
		memset(net,0,sizeof(net));
		memset(num,0,sizeof(num));
		gets(plug[0]);
		for(i=1;i<=n;i++) {
			gets(plug[i]);
		}
		tn = n;
		scanf("%d", &m);
		gets(plug[0]);
		for(i=0;i<m;i++) {
			scanf("%s %s", device, dplug);
			int pos = find(dplug);
			if(pos == -1) {
				strcpy(plug[n+1], dplug);
				num[n+1] ++;
				n ++;
			}
			else {
				num[pos] ++;
			}
		}
		tm = n;

		scanf("%d", &k);
		gets(plug[0]);
		for(i=0;i<k;i++) {
			scanf("%s %s", adap, dplug);
			int pos1 = find(adap);
			if(pos1 == -1) {
				strcpy(plug[n+1], adap);
				n ++;
				pos1 = n;
			}
			int pos2 = find(dplug);
			if(pos2 == -1) {
				strcpy(plug[n+1], dplug);
				n ++;
				pos2 = n;
			}
			net[pos1][pos2] = INT_MAX;
		}

		for(i=1;i<=tm;i++) {
			net[0][i] = num[i];
		}
		for(i=1;i<=tn;i++) {
			net[i][n+1] = 1;
		}
		printf("%d\n", m - Ford_Fulkerson());
	}
}