无向连通网络，去掉一个边集可以使其变成两个连通分量则这个边集就是割集，最小割集当然就权和最小的割集。
使用最小切割最大流定理：
1.min=MAXINT,确定一个源点
2.枚举汇点
3.计算最大流，并确定当前源汇的最小割集，若比min小更新min
4.转到2直到枚举完毕
5.min即为所求输出min
复杂度很高：枚举汇点要O(n)，最短增广路最大流算法求最大流是O((n^2)m)复杂度，在复杂网络中O(m)=O(n^2)，算法总复杂度就是O(n^5)；哪怕采用最高标号预进流算法求最大流O((n^2)(m^0.5))，算法总复杂度也要O(n^4) 所以用网络流算法求解最小割集复杂度不会低于O(n^4)。
------------------------------------------使用Stoer-Wagner算法
1.min=MAXINT，固定一个顶点P
2.从点P用“类似”prim的s算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边
3.计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min
4.合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并，这个好理解吧？）
5.转到2，合并N-1次后结束
6.min即为所求，输出min
prim本身复杂度是O(n^2)，合并n-1次，算法复杂度即为O(n^3)，如果在prim中加堆优化，复杂度会降为O((n^2)logn)
帮助理解（reference http://www.cnblogs.com/ihopenot/p/5986772.html）：考虑任意两个点为s，t，如果全局最小割中s，t不在一个集合中，那么显然全局最小割即为s-t最小割。否则我们将s，t缩成一个节点对于答案是没有影响的。基于这一点，每次将问题规模减小后求解。一开始选择的节点是作为s-t的中间节点集，因为每次扩展是选取联系度最大的点扩展，所以中间节点集中点互相间的联系度是大于st到中间点集的联系度的，而最后加入的点t的联系度是最小的，所以最小割即为这个点的联系度，即为s通过中间节点集到t的流量加上s直接到t的流量。所以就证明了每次拓展求出的是s-t的最小割。
--------------------------------------------代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define MAX_N 30
#define INF 0x3f3f3f3f int G[MAX_N][MAX_N];
int v[MAX_N]; // v[i]代表节点i合并到的顶点
int w[MAX_N]; // 定义w(A,x) = ∑w(v[i],x)，v[i]∈A
bool visited[MAX_N]; // 用来标记是否该点加入了A集合
int squ[MAX_N]; //记录移除的节点次序
int index; int stoer_wagner(int n)
{
int min_cut = INF,r=0;
for (int i = 0; i < n; ++i)
{
v[i] = i; // 初始还未合并，都代表节点本身
} while (n > 1)
{
int pre = 0; // pre用来表示之前加入A集合的点（在t之前一个加进去的点）
memset(visited, 0, sizeof(visited));
memset(w, 0, sizeof(w));
for (int i = 1; i < n; ++i) //求出 某一轮最大生成树的最后两个节点，并且去除最后的t，将与t连接的边归并
{
int k = -1;
for (int j = 1; j < n; ++j) // 选取V-A中的w(A,x)最大的点x加入集合
{
if (!visited[v[j]])
{
w[v[j]] += G[v[pre]][v[j]];
if (k == -1 || w[v[k]] < w[v[j]])
{
k = j;
}
}
} visited[v[k]] = true; // 标记该点x已经加入A集合
if (i == n - 1) // 若|A|=|V|（所有点都加入了A），结束
{
const int s = v[pre], t = v[k]; // 令倒数第二个加入A的点（v[pre]）为s，最后一个加入A的点（v[k]）为t
cout<<t<<"--->"<<s<<endl;
squ[r++]=t;
if(w[t]<min_cut)
{
min_cut=w[t];
index=r;
}
//min_cut = min(min_cut, w[t]); // 则s-t最小割为w(A,t)，用其更新min_cut
for (int j = 0; j < n; ++j) // Contract(s, t)
{
G[s][v[j]] += G[v[j]][t];
G[v[j]][s] += G[v[j]][t];
}
v[k] = v[--n]; // 删除最后一个点（即删除t，也即将t合并到s）
}
// else 继续
pre = k;
}
}
return min_cut;
} int main(int argc, char *argv[])
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
memset(G, 0, sizeof(G));
while (m--)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u][v] += w;
G[v][u] += w;
}
int z=n;
//printf("%d\n", stoer_wagner(n));
cout<<"\r\n归并的步骤为："<<endl;
int res=stoer_wagner(n);
cout<<"\r\n最小割的总权值为： "<<res<<"\r\n图划分为部分A：";
//cout<<"图划分为部分A：";
for(int i=0;i<z;i++)
{
if(i==index)
cout<<"部分B：";
cout<<squ[i]<<" ";
}
}
return 0;
}
---------------------------------------示例
