Stoer Wagner 算法

发布于 2018-12-25  375 次阅读

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
相信大家看到这里一定是懵逼的...那么建议大家先阅读代码，然后结合论文食用。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#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;
}

一个OIer。