POJ 2914 Minimum Cut （最小割模板题）

POJ 2914 Minimum Cut （最小割模板题）

题解：最小割模板题。

可以用网络流？不行的。枚举举汇点要O(n)，最短增广路最大流算法求最大流是O(n2m)复杂度，在复杂网络中O(m)=O(n2)，算法总复杂度就是O(n5)；就算你用其他求最大流的算法，算法总复杂度也要O(n4)。所以用网络流算法求解最小割集复杂度不会低于O(n4)。所以就要用Stoer_Wagner算法。算法复杂度为O(n3)。如果在prim中加堆优化，复杂度会降为O(n2logn)。

讲一下，Stoer_Wagner算法： Stoer_Wagner算法是求无向图全局最小割的一个有效算法，最坏时间复杂度O(n3)，主要思想是先找任意2点的最小割，然后记录下这个最小割，再合并这2个点。这样经过n−1次寻找任意2点最小割，每次更新全局最小割，最后整张图缩成一个点，算法结束，所保存下来的最小割就是全局最小割。

Stoer−Wagner的正确性： 设S和T是图G的2个顶点，图G的全局最小割要么是S−T的最小割，此时S和T在G的全局最小割的2个不同的子集中，要么就是G中将S和T合并得的的新图G′的全局最小割，此时S和T在G的全局最小割的同一个子集中。所以只需要不断求出当前图中任意2个点的最小割，然后合并这2$2$个点。不断缩小图的规模求得最小割。

代码：

//#include #include #include #include #include #define N 500+10#define INF 0x3f3f3f3fusing namespace std;int mp[N][N];int v[N]; // v[i]代表节点i合并到的顶点int dis[N];//dis数组用来表示该点与A集合中所有点之间的边的长度之和bool vis[N]; //是否已并入集合int n,m;int Stoer_Wagner(int n){ int i, j, res = INF; for(i = 0; i < n; i ++) v[i] = i;保存顶点 ，固定顶点为自己 while(n > 1) { //pre用来表示之前加入A集合的点 //我们每次都以0点为第一个加入A集合的点 int k = 1, pre = 0; for(i = 1; i < n; i ++){ dis[v[i]] = mp[v[0]][v[i]]; if(dis[v[i]] > dis[v[k]]) k = i; } memset(vis, 0, sizeof(vis)); vis[v[0]] = true;//标记该点已经加入A集合 for(i = 1; i < n; i ++) { if(i == n-1)//最后一次加入的点就要更新答案 { res = min(res, dis[v[k]]); for(j = 0; j < n; j ++) //将该点合并到pre上，相应的边权就要合并 { mp[v[pre]][v[j]] += mp[v[j]][v[k]]; mp[v[j]][v[pre]] += mp[v[j]][v[k]]; } v[k] = v[-- n];//删除最后一个点 } vis[v[k]] = true; pre = k; k = -1; for(j = 1; j < n; j ++) if(!vis[v[j]]) { //将上次求的 k 加入集合，合并与它相邻的边到割集 dis[v[j]] += mp[v[pre]][v[j]]; if(k == -1 || dis[v[k]] < dis[v[j]]) k = j; } } } return res;}int main(){ while(~scanf("%d%d", &n, &m)) { memset(mp, 0, sizeof(mp)); int a, b, c; for(int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &c); //从 0 开始 mp[a][b] += c; mp[b][a] += c; } printf("%d\n", Stoer_Wagner(n)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。