POJ2914

题意

给出一个有边权的无向图，求最小割。

思路

如果按照网络流的做法，通过求最大流来求最小割。就需要确定一个源点然后枚举汇点，这样的复杂度极高，据说有O(n5)。所以这个题并不是这么做，而是用stoer_wagner算法。这一算法在求最小割的问题中具有普适性。

stoer_wagner算法

算法思路

整体思路和求最小生成树的prim算法有些相似，不过这里求的“有点像”“最大生成树”。构造一个集合A，一开始将任意一个点加入。之后重复地从剩下的点中选择点x，使集合A到x的流最大（也就是A内点到x的流之和），把x加入A中。把x加入A的时候要记得更新A到剩下点的流。一直重复到所有点都加入A中，则最后一个点的所有边的权值之和，就是以它为汇点，最后一个加入A的点为源点的最小割。此时更新最小割的值，然后将这两个点合并成一个点，重复上述操作，直到所有的点都合并成了一个点。此时便获得了全局最小割的值。

合并操作合法嘛？

合法。最后的两个点有两种情况，一种是它们在全局最小割的同一端，将它俩合并并不影响最小割的值；一种是它俩在最小割的两端，如果是这样那么这一次更新全局最小割就已经得到了最终答案。

为什么最后一个点的所有边权值之和就是到前一个点的最小割？

如果不切断这其中的任何一条边，最后一个点都能和前一个点连起来。而且每次都选流最大的，最后一个点就是整个图中到其他点的流之和最小的点。

其他点可以嘛？

其他点不一定满足。如下图 第一次更新中，最后一个点是6，前一个点是5，此时6的边权之和是5到6的最小割，这没问题。但是换成0到6，就显然不对了。至于这原理，现在还没想明白。

它还满足最小割是最大流的规律嘛？

满足。从最后一个点出发的流必定都能流进前一个点。因为前一个点在A中的接口数不小于最后一个点。

算法流程

设最小割cut=INF, 任选一个点s到集合A中, 定义W(A, p)为A中的所有点到A外一点p的权总和.对刚才选定的s, 更新W(A,p)(该值递增).选出A外一点p, 且W(A,p)最大的作为新的s, 若A!=G(V), 则继续2.把最后进入A的两点记为s和t, 用W(A,t)更新cut.合并st，即新建顶点u, 边权w(u, v)=w(s, v)+w(t, v), 删除顶点s和t, 以及与它们相连的边.若|V|!=1则继续1.

题目链接

http://poj.org/problem?id=2914

AC代码

#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn = 500 + 10; const int inf = 0x3f3f3f3f; int n, m; int G[maxn][maxn];//存图 int w[maxn];//集合A到剩余各点的流 bool vis[maxn];//点是否已经加入A bool com[maxn];//点时候已经被合并删除 int stoer_wagner() { memset(com, false, sizeof com);//多样例 int min_cut = inf;//全局最小割置为无穷 //k表示几个点被合并后删除了 for(int k= 0; k< n-1; k++) { memset(w, 0, sizeof w);//集合A到各点的流置为0 memset(vis, false, sizeof vis);//加入A的标记置为0 int s, t = 0;//前一个点，最后一点，这里实际是把s置为0 //不断把点加入A //n-k表示此时还有多少个没删除的有效点 //i表示集合A中已经有了几个点 //初始是1，因为默认将0点加入A中 for(int i= 1; i< n-k; i++) { s = t, t = -1;//敲黑板 //枚举找出剩下的点中到A的流最大的 //因为0已经第一个进入A了，所以这里从1开始枚举 for(int j= 1; j< n; j++) { //首先更新w[j] w[j] += G[s][j]; //没加入A，没被删除，流大 if(!vis[j] && !com[j] && (t == -1 || w[t] < w[j])) t = j; } //t加入A vis[t] = true; } //更新全局最小割 if(min_cut > w[t]) min_cut = w[t]; //合并删除点t for(int i= 0; i< n; i++) { G[s][i] += G[t][i]; G[i][s] += G[i][t]; } com[t] = true; } return min_cut; } int main() { while(scanf("%d %d", &n, &m) != EOF) { memset(G, 0, sizeof G);//多样例 for(int i= 0; i< m; i++) { int x, y, c; scanf("%d %d %d", &x, &y, &c); G[x][y] += c; G[y][x] += c; } cout << stoer_wagner() << endl; } return 0; }