I tried all of the datas in USACO training, and passed all of them.

Nevertheless, I got WA for so many times...

Here's my code: (search using DFS, because BFS(Dijkstra) is troublesome-)

#include <stdio.h>
#include <memory.h>
#define _min(a,b) (((a)<(b))?(a):(b))

int from[401];
__int64 matrix[401][401];
int N;

__int64 ans;

void i_stream()
{
	int edgeN;
	scanf("%d %d", &edgeN, &N);
	int i;
	int st, ed;
	int val;
	for (i = 0;i < edgeN;i++)
	{
		scanf("%d %d", &st, &ed);
		scanf("%d", &val);
		matrix[st - 1][ed - 1] += val;
	}
}

__int64 fill(int pl, __int64 val)
{
	if (pl == N - 1)
	{
		return val;
	}

	int i;
	__int64 fval;
	for (i = 0;i < N;i++)
	{
		if (from[i] != -1)
			continue;
		if (matrix[pl][i] == 0)
			continue;
		from[i] = pl;
		fval = fill(i, _min(val, matrix[pl][i]));
		if (fval == 0)
			continue;
		matrix[i][pl] += fval;
		matrix[pl][i] -= fval;
		return fval;
	}

	return 0;
}

void process()
{
	__int64 val;
	for (;;)
	{
		memset(from, 0xFF, sizeof(from));

		from[0] = -2;

		if ((val = fill(0, 0x3FFFFFFF)) == 0)
			break;

		ans += val;
	}
}

void o_stream()
{
	printf("%I64d\n", ans);
}

int main()
{
	i_stream();
	process();
	o_stream();

	return 0;
}

• there are multiple test cases in the input. (1449) frkstyc 2006-06-04 15:59:31
  • ... (13) beingryu 2006-06-04 16:07:13