http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1089

#include <iostream>
#include <queue>
using namespace std;

class Graph
{
public:
	int capacity, flow;
};
const int N = 201;
const int INFINITE = 0x7f7f7f7f;
int residual[N][N], n, m, minaugement;
Graph graph[N][N];
int start, end, maxflow, pre[N];
bool used[N];

void findaugementpath ()
{
	queue <int> q;
	memset ( pre, 0, sizeof ( pre ) );
	memset ( used, false, sizeof ( used ) );
	memset ( residual, 0, sizeof ( residual ) );
	used[start] = true;
	pre[start] = start;
	q.push( start );

	while ( !q.empty() && pre[end] == 0 )
	{
		int node = q.front();
		q.pop();

		for ( int v = 1; v <= m; v++ )
			if ( !used[v] )
			{
				int value;
				if ( ( value = graph[node][v].capacity - graph[node][v].flow ) > 0 )
				{
					pre[v] = node;
					q.push( v );
					used[v] = true;
					residual[node][v] = value;
				}
				else if ( graph[v][node].flow > 0 )
				{
					pre[v] = node;
					q.push( v );
					used[v] = true;
					residual[node][v] = graph[v][node].flow;
				}
			}
	}
}

void augementflow ()
{
	if ( pre[end] == 0 )
	{
		minaugement = 0;
		return;
	}

	int i = end, j = INFINITE;
	while ( i != start )
	{
		j = j < residual[pre[i]][i] ? j : residual[pre[i]][i];
		i = pre[i];
	}

	minaugement = j;
}

void updateflow ()
{
	if ( pre[end] == 0 )
		return;

	int i = end;
	while ( i != start )
	{
		if ( graph[pre[i]][i].capacity - graph[pre[i]][i].flow > 0 )
			graph[pre[i]][i].flow += minaugement;
		else if ( graph[i][pre[i]].flow > 0 )
			graph[pre[i]][i].flow += minaugement;
		i = pre[i];
	}
}

void Ford_Fullerson ()
{
	start = 1, end = m;
	maxflow = 0;

	while ( true )
	{
		findaugementpath ();
		augementflow ();

		maxflow += minaugement;

		if ( minaugement > 0 )
			updateflow ();
		else break;
	}

	printf ( "%d\n", maxflow );
}

int main ()
{
//	freopen ( "1273.txt", "r", stdin );
	while ( scanf ( "%d%d", &n, &m ) != -1 )
	{
		int s, t, w;
		memset ( graph, 0, sizeof ( graph ) );
		for ( int i = 0; i < n; i++ )
		{
			scanf ( "%d%d%d", &s, &t, &w );
			graph[s][t].capacity += w;
		}

		Ford_Fullerson ();
	}
	return 0;
}

• Re:下面的代码在POJ可以AC，可是在XOJ（链接在内）确实WA了。。。请牛人指教。 (5095) IceKingdom 2009-01-24 10:45:58