Stoer Wagner 算法主要是解决无向图最小割的问题。
给定一张无向图，每一条边都有其花费，求最少能使这张图不连通应割掉的边数。
原作者论文，侵删
解题思路
首先我们可以使用网络流暴力跑，也就是随机一个源点然后枚举汇点跑最大流那种，但是时间复杂度有点高，上界是 $O(n^3m)$。
于是 就有了 Stoer Wagner 算法来解决这个问题。
我们先描述一下这个算法的一般流程：
1. $min = INF$，固定一个顶点 $P$
2. 从点 $P$ 用 “类似” prim 的算法扩展出 “最大生成树” ，记录最后扩展的顶点和最后扩展的边
3. 计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比 min 小更新 min
4. 合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并，这个好理解吧？）
5. 转到 $2$，合并 N-1 次后结束
6. min 即为所求，输出 min
相信大家看到这里一定是懵逼的…那么建议大家先阅读代码，然后结合论文食用。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <algorithm> #include <iostream> #include <cstring> #include <climits> #include <cstdio> #include <vector> #include <cstdlib> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define Re register #define LL long long #define U unsigned #define FOR(i,a,b) for(Re int i = a;i <= b;++i) #define ROF(i,a,b) for(Re int i = a;i >= b;--i) #define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c) #define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c) #define CLR(i,a) memset(i,a,sizeof(i)) #define BR printf("--------------------\n") #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1000+5; int f[MAXN][MAXN],dist[MAXN]; bool vis[MAXN],del[MAXN]; int N,M; inline void init(){ CLR(f,0);CLR(del,false); } int contract(int &s,int &t){ int min=0; CLR(dist,0);CLR(vis,0); FOR(i,1,N){ int k = -1,max = -1; FOR(j,1,N){ if(!del[j] && !vis[j] && dist[j] > max){ k = j;max = dist[j]; } } if(k == -1) return min; s = t,t = k; min = max; vis[k] = true; FOR(j,1,N){ if(!del[j] && !vis[j]) dist[j] += f[k][j]; } } return min; } int SW(){ int min = INT_MAX; FOR(i,1,N-1){ int s,t; min = std::min(min,contract(s,t)); del[t] = true; if(min == 0) return 0; FOR(j,1,N) if(!del[j]) f[s][j] = (f[j][s] += f[j][t]); } return min; } inline void Solve(){ init(); FOR(i,1,M){ int u,v,w;scanf("%d%d%d",&u,&v,&w); u++;v++; f[u][v] = (f[v][u] += w); } printf("%d\n",SW()); } int main(){ while(~scanf("%d%d",&N,&M)) Solve(); return 0; } |
发表评论