最标准的最小割算法应用题目。

核心思想就是缩边：先缩小最大的边。然后缩小次大的边。依此缩小

基础算法：Prime最小生成树算法

只是本题測试的数据好像怪怪的，相同的算法时间执行会区别非常大，并且一样的代码替换。竟然会WA。系统出错的几率非常小。难倒測试系统本题会有错误？

懒得继续測试这道题的系统了，反正算法正确。AC。

#include <stdio.h>

#include <string.h>

#include <limits.h>

const int MAX_N = 500;

int N, M, A, B, C, S, T;

int gra[MAX_N][MAX_N], dis[MAX_N];

bool vis[MAX_N], delVer[MAX_N];

inline int min(int a, int b) { return a < b ? a : b; }

int search(int V)	//V为计算剩下多少顶点了

{

	memset(vis, 0, sizeof(vis));

	memset(dis, 0, sizeof(dis));

	int curMax = 0, cur = 0;

	S = 0, T = 0;

	for (int i = 1; i < V; i++)

	{

		curMax = 0;

		for (int j = 1; j < N; j++)

		{

			if (!vis[j] && !delVer[j]) dis[j] += gra[cur][j];

		}

		for (int j = 1; j < N; j++)

		{

			if (!vis[j] && !delVer[j] && dis[j] > curMax)

			{

				curMax = dis[j];

				cur = j;

			}

		}

		vis[cur] = true;

		if (T == cur) return 0; //图不相连。提前结束循环，割点为0

		S = T; T = cur;		//目的得到最后和倒数第二节点。以便进行缩图

	}

	return curMax;

}

//核心思想：先缩小最大的边，然后缩小次大的边，依此缩小

int Stoer_Wagner()

{

	memset(delVer, 0, sizeof(delVer));

	int minCut = INT_MAX;

	for (int v = N; v > 1; v--) //共N-1条边, 当前v个点

	{

		minCut = min(minCut, search(v));

		if (minCut == 0) return 0;	//一点优化，提前结束

		delVer[T] = true;

		for (int i = 0; i < N; i++)

			if (!delVer[i]) gra[S][i] = gra[i][S] += gra[T][i];

	}

	return minCut == INT_MAX ? 0 : minCut;//仅仅有一个顶点的时候返回0

}

int main()

{

	while (~scanf("%d %d", &N, &M))

	{

		memset(gra, 0, sizeof(gra));

		for (int i = 0; i < M; i++)

		{

			scanf("%d %d %d", &A, &B, &C);

			gra[B][A] = gra[A][B] += C;

		}

		printf("%d\n", Stoer_Wagner());

	}

	return 0;

}