Stoer-Wagner无向图全局最小割（hduoj 3691 Nubulsa Expo）

题意：

一张n个点m条边的无向图，每个点都有一个最大流量，给定起点S，问如何选取终点T，使得最大流最大

翻译一下：

一张n个点m条边的无向联通图，你要割掉一些边使整张图不连通，但是割掉每条边都需要一定费用，求最小费用

即全局最小割

最小割集Stoer-Wagner算法：

①选择一个顶点p，用prim求出类似最大生成树，其中bet[x]为x点到所有已扩展点的距离之和

②令最后扩展的两个点为S和T，记录ans = min(ans, bet[T])

③合并S到T为一个点，当然路径也要合并

④继续1步骤直到图中只剩下一个点

复杂度：考虑有重边

如果是用邻接表复杂度为O(n²m)

邻接矩阵O(n^3)

如果用堆优化可将复杂度降低为O(nmlogn)

证明：https://wenku.baidu.com/view/fdb484c3bb4cf7ec4afed08b.html

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int road[305][305], v[305], vis[305], bet[305];
int main(void)
{
	int a, b, c, n, m, s, i, j, ans, k, temp, t;
	while(scanf("%d%d%*d", &n, &m), n!=0)
	{
		memset(road, 0, sizeof(road));
		while(m--)
		{
			scanf("%d%d%d", &a, &b, &c);
			road[a][b] += c;
			road[b][a] += c;
		}
		ans = 2147483647;
		for(i=1;i<=n;i++)
			v[i] = i;
		while(n>1)
		{
			memset(vis, 0, sizeof(vis));
			for(i=1;i<=n;i++)
				bet[v[i]] = road[v[1]][v[i]];
			vis[v[1]] = 1;
			for(i=2;i<=n;i++)
			{
				k = -1;
				temp = 0;
				for(j=1;j<=n;j++)
				{
					if(vis[v[j]]==0 && bet[v[j]]>k)
					{
						k = bet[v[j]];
						temp = j;
					}
				}
				vis[v[temp]] = 1;
				if(i==n-1)
					s = temp;
				if(i==n)
					t = temp;
				for(j=1;j<=n;j++)
				{
					if(vis[v[j]]==0)
						bet[v[j]] += road[v[temp]][v[j]];				//bet[x]为x点到所有已扩展点的距离之和
				}
			}
			ans = min(ans, bet[v[t]]);
			for(i=1;i<=n;i++)
			{
				road[v[s]][v[i]] += road[v[t]][v[i]];
				road[v[i]][v[s]] = road[v[s]][v[i]];
			}
			v[temp] = v[n];
			n--;
		}
		printf("%d\n", ans);
	}
	return 0;
}