题目链接：

思路：算法基于这样一个定理：对于任意s, t   V ∈ ，全局最小割或者等于原图的s-t 最小割，或者等于将原图进行 Contract(s, t)操作所得的图的全局最小割。 算法框架： 

1. 设当前找到的最小割MinCut 为+∞ 。

2. 在 G中求出任意 s-t 最小割 c，MinCut = min(MinCut, c)   。

3. 对 G作 Contract(s, t)操作，得到 G'=(V', E')，若|V'| > 1，则G=G'并转 2，否则MinCut 为原图的全局最小割。

Contract 操作定义： 

若不存在边(p, q)，则定义边(p, q)权值w(p, q) = 0 

Contract(a, b): 删掉点 a, b 及边(a, b)，加入新节点 c，对于任意 v V ∈ ，w(v, c) = w(c, v) = w(a, v) + w(b, v).

求 G=(V, E)中任意 s-t 最小割的算法： 

定义w(A, x) = ∑w(v[i], x)，v[i] ∈ A  

定义 Ax 为在x 前加入 A 的所有点的集合（不包括 x） 

1. 令集合 A={a}，a为 V中任意点 

2. 选取 V - A中的 w(A, x)最大的点 x加入集合 A 

3. 若|A|=|V|，结束 

令倒数第二个加入 A的点为 s，最后一个加入 A的点为 t，则s-t 最小割为 w(At, t)。

贴下大牛的模版：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define MAXN 555 7 #define inf 1<<30 8  9 int v[MAXN],dist[MAXN];10 int map[MAXN][MAXN];11 bool vis[MAXN];12 int n,m;13 14 //求全局最小割的Stoer_Wanger算法15 int Stoer_Wanger(int n)16 {17     int res=inf;18     for(int i=0;i
          
           1){20         int k=0,pre=0;//pre用来表示之前加入A集合的点，我们每次都以0点为第一个加入A集合的点21         memset(vis,false,sizeof(vis));22         memset(dist,0,sizeof(dist));23         for(int i=1;i