drainage ditches(high_label_preflow_push)o(v^2e).cpp

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

//high label preflow push O(V^2*E)
#include <cstdio>
#include <cstdlib>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

const int NMAX = 210;
//earn盈余,net剩余网络,high高度
int earn[NMAX], net[NMAX][NMAX], high[NMAX];
int n, m;
queue<int> SQ;

void push(int u, int v)
{
	int ex = min(earn[u], net[u][v]);
	earn[u] -= ex;
	net[u][v] -= ex;
	earn[v] += ex;
	net[v][u] += ex;
}

void relable(int u)
{
	int i, mmin = INT_MAX;
	for(i=0;i<=n;i++) {
		if(net[u][i] > 0 && high[i] >= high[u]) {
			mmin = min(mmin, high[i]);
		}
	}
	high[u] = mmin +1;
}

void discharge(int u)
{
	int i;
	int vn;
	while(earn[u] > 0) {
		vn = 0;
		for(i=0;i<=n && earn[u] > 0;i++) {
			if(net[u][i] > 0 && high[u] == high[i]+1) {
				push(u,i);
				vn ++;
				if(i != n) {
					SQ.push(i);
				}
			}
		}
		if(vn == 0) {
			relable(u);
		}
	}
}

void init_preflow()
{
	int i;
	memset(high,0,sizeof(high));
	memset(earn,0,sizeof(earn));
	while(!SQ.empty()) {
		SQ.pop();
	}
	high[0] = n+1;//s = 0; t = n+1;
	net[0][1] = INT_MAX;//virtual s and t
	net[n][n+1] = INT_MAX;
	n ++;
	for(i=1;i<=n;i++) {
		if(net[0][i] > 0) {
			earn[i] = net[0][i];
			earn[0] -= net[0][i];
			net[i][0] = net[0][i];
			net[0][i] = 0;
			if(i != n) {
				SQ.push(i);
			}
		}
	}
}

int high_label_preflow_push()
{
	int i,j;

	init_preflow();
	while(!SQ.empty()) {
		int overp = SQ.front();
		SQ.pop();
		change(overp);
	}
	return earn[n];
}

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