题目链接：
?id=2914
题目大意：
提一个无向有重边的图，有重边的边权累加起来，求全局最小割。
思路：
一个无向连通图，，去掉一个边集可以使其变成两个连通分量则这个边集就是割集。最小割
集当然就是权和最小的割集。
这是一个最简单的全局最小割模板题。直接套上模板就可以了。来说说Stoer-Wangner算
法吧。
Stoer-Wangner算法：
对于图中的任意两个顶点u和v，若u，v属于最小割的同一个集合中，那么僵顶点u和顶点
v合并后并不影响图的最小割。那么，如果能求出图中某两个顶点之间的最小割，更新答案
后合并这两个顶点继续求最小割，到最后就得到答案了。问题就转变成了求某两点之间的
最小割。
具体步骤：参考ACM-ICPC程序设计系列——图论 P142-146
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 550;const int MAXM = MAXN*MAXN>>1;int N,M;int Map[MAXN][MAXN],Dist[MAXN],Node[MAXN],vis[MAXN];int Stowag(int N){int Maxj,pre,m,ans;memset(Dist,0,sizeof(Dist));memset(vis,0,sizeof(vis));for(int i = 0; i < N; ++i)Node[i] = i;while(N > 1){m = -1;Maxj = 1;for(int i = 1; i < N; ++i){Dist[Node[i]] = Map[Node[0]][Node[i]];vis[Node[i]] = 0;if(Dist[Node[i]] > m){m = Dist[Node[i]];Maxj = i;}}pre = 0;vis[Node[0]] = 1;for(int j = 1; j < N; ++j){vis[Node[Maxj]] = 1;if(j == N-1){ans = min(ans,m);for(int i = 0; i < N; ++i){Map[Node[pre]][Node[i]] += Map[Node[Maxj]][Node[i]];Map[Node[i]][Node[pre]] += Map[Node[Maxj]][Node[i]];}Node[Maxj] = Node[–N];}else{pre = Maxj;m = -1;for(int i = 1; i < N; ++i){if(!vis[Node[i]]){Dist[Node[i]] += Map[Node[pre]][Node[i]];if(Dist[Node[i]] > m){m = Dist[Node[i]];Maxj = i;}}}}}}return ans;}int main(){int u,v,w;while(~scanf("%d%d",&N,&M)){memset(Map,0,sizeof(Map));for(int i = 0; i < M; ++i){scanf("%d%d%d",&u,&v,&w);Map[u][v] += w;Map[v][u] += w;}printf("%d\n",Stowag(N));}return 0;}
一个人最大的破产是绝望，最大的资产是希望。
