drainage ditches(ford_forlkerson)o(ve^2).cpp

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

//Edmonds-Karp O(V*E^2) 
#include <cstdio>
#include <cstdlib>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

const int NMAX = 210;
int net[NMAX][NMAX];
int path[NMAX];
int n, m;

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

	while(!SQ.empty()) {
		int now = SQ.front();
		SQ.pop();
		if(now == m) {
			break ;
		}
		for(i=2;i<=m;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[m] == -1) {
		return -1;
	}
	return neck[m];
}

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

int main()
{
	int i,j;
	while(scanf("%d %d", &n, &m)==2) {
		memset(net,0,sizeof(net));
		for(i=0;i<n;i++) {
			int s,e,c;
			scanf("%d %d %d", &s, &e, &c);
			net[s][e] += c;
		}
		printf("%d\n", Ford_Fulkerson());
	}
}