pku1273.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define SIZE 210
#define INF 100000000

int p[SIZE][SIZE];
int f[SIZE][SIZE];
int N, M;
int Q[SIZE], fp[SIZE];

int BFS()
{
	int head, tail, ans;
	int qp, i;
	head = 0;
	tail = 1;
	memset(fp, 0, sizeof(fp));
	fp[1] = 1;
	Q[head] = 1;
	while (head < tail)
	{
		qp = Q[head];
		for (i = 0; i <= M; i++)
		{
			if (!fp[i] && f[qp][i] < p[qp][i])
			{
				fp[i] = qp;
				Q[tail++] = i;
				if (i == M)
					break;
			}
		}
		head++;
	}
	if (fp[M] == 0)
		return 0;
	else
	{
		ans = INF;
		i = M;
		while (fp[i] != i)
		{
			if (ans > p[fp[i]][i] - f[fp[i]][i])
				ans = p[fp[i]][i] - f[fp[i]][i];
			i = fp[i];
		}
		i = M;
		while (fp[i] != i)
		{
			f[fp[i]][i] += ans;
			f[i][fp[i]] = -f[fp[i]][i];
			i = fp[i];
		}
	}
	return ans;
}

int maxflow()
{
	int ans, add;
	ans = 0;
	memset(f, 0, sizeof(f));
	while (1)
	{
		add = BFS();
		if (add == 0)
			return ans;
		ans += add;
	}
}

void Solve()
{
	int i, j, s, e, c;
	memset(p, 0, sizeof(p));
	for (i = 0; i < N; i++)
	{
		scanf("%d %d %d", &s, &e, &c);
		p[s][e] += c;
	}
	printf("%d\n", maxflow());
}

int main()
{
	while (EOF != scanf("%d %d", &N, &M) && (N || M))
		Solve();
	return 0;
}