1228.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1228 on 2006-11-09 at 11:13:16 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 128;
const int INF = 1 << 28;

class Network {
private:
	int v, s, t;
	int cap[N][N], flow[N][N], prev[N];
	bool bfs();
public:
	bool build();
	int maxFlow(int, int);
};
bool Network::build() {
	int m, np, nc;
	int a, b, l;
	if(scanf("%d %d %d %d", &v, &np, &nc, &m) != 4) return false;
	memset(cap, 0, sizeof(cap)); v += 2;
	for(int i = 0; i < m; i++) {
		scanf("\n(%d,%d)%d", &a, &b, &l);
		cap[a+2][b+2] = l;
	}
	for(int i = 0; i < np; i++) {
		scanf("\n(%d)%d", &a, &l);
		cap[0][a+2] = l;
	}
	for(int i = 0; i < nc; i++) {
		scanf("\n(%d)%d", &a, &l);
		cap[a+2][1] = l;
	}
	return true;
}
bool Network::bfs() {
	queue<int> Q;
	bool vst[N] = { false };
	Q.push(s); vst[s] = true;
	while(!Q.empty()) {
		int u = Q.front(); Q.pop();
		for(int i = 0; i < v; i++)
			if(!vst[i] && cap[u][i] != flow[u][i]) {
				Q.push(i); prev[i] = u; vst[i] = true;
				if(i == t) return true;
			}
	}
	return false;
}
int Network::maxFlow(int ss, int tt) {
	s = ss; t = tt;
	memset(flow, 0, sizeof(flow));
	int f = 0;
	while(bfs()) {
		int ex = INF;
		for(int c = t; c != s; c = prev[c]) ex <?= cap[prev[c]][c]-flow[prev[c]][c];
		for(int c = t; c != s; c = prev[c]) { flow[prev[c]][c] += ex; flow[c][prev[c]] -= ex; }
		f += ex;
	}
	return f;
}

int main()
{
	Network net;
	
	while(net.build()) printf("%d\n", net.maxFlow(0, 1));
	
	return 0;
}