我们先从算法简介讲起……

算法简介

Stoer-Wagner 算法在 1995 年由 Stoer 和 Wagner 共同提出，是一种通过递归的方式来解决无向正权图上的全局最小割问题的算法。

概念

• 割：对于一个无向图 $G

  ( V , E )，令 C U T 表示一些边的集合，若从 G 中删去 C U T 的所有边，使得 G 不再连通，我们就称 C U T 集合是 G$ 的割。

• 最小割：一个去掉后可以使 G 变成两个连通分量，且边权和最小的边集的边权和。
• # 步骤 1. 在图 $G$ 中确定两点 $s$，$t$。 2. 求出 $S − T$ 最小割。 3. 合并 $s$，$t
  • 删除 s，t 之间的边。
  • 对于 \frac{G}{\{ s , t \}} 中任意一点 k，删除 ( t , k )。
  • d i s t ( t , k )$。 4. 若 $| V | ＞ 1$，返回 $step$ $1$。 5. 输出最小值。

合并的过程非常像 Prim 求最小生成树的过程。

代码

#include<bits/stdc++.h>
using namespace std;
const int ma=605;
const int INF=(1<<29);
int mp[ma][ma],dis[ma],fa[ma],size[ma],n,m;;
bool vis[ma],re[ma];
inline int get(int x){
    if(fa[x]==x)    return x;
    return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){
    int f1=get(x);
    int f2=get(y);
    if(f1!=f2){
        fa[f1]=f2;
        size[f2]+=size[f1];
    }
}
inline int contract(int &s,int &t){
    int minn=INF;//最小割 
    memset(dis,0,sizeof(dis));
    memset(vis,false,sizeof(vis));
    //类似于 Prim 求最小生成树的步骤 
    for(register int i=1;i<=n;i++){
        int maxx=-INF,u=-1;
        for(register int j=1;j<=n;j++){
            if(re[j]==false && vis[j]==false && dis[j]>maxx){
                maxx=dis[j];
                u=j;
            }
        }
        if(u==-1)return minn;
        s=t;
        t=u;
        minn=maxx;
        vis[u]=true;
        for(register int j=1;j<=n;j++)if(re[j]==false && vis[j]==false)dis[j]+=mp[u][j];
    } 
    return minn;
}
inline int Stoer_Wagner(){
    int minn=INF;
    int s,t,ans;
    for(register int i=1;i<=n-1;i++){//循环 n - 1 次
        ans=contract(s,t);
        re[t]=true;
        minn=min(minn,ans);
        if(minn==0)return 0;
        for(register int j=1;j<=n;j++)
            if(re[j]==false){
                mp[j][s]+=mp[j][t];
                mp[s][j]=mp[j][s];
            }
    }  
    return minn;
}
int main(void){
    scanf("%d%d",&n,&m);
    if(m<n-1)puts("0");//很明显将导致不连通
    else{
        for(register int i=1;i<=n;i++){
            fa[i]=i;
            size[i]=1;
        }
        for(register int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            if(get(u)!=get(v))merge(u,v);
            mp[u][v]+=w;
            mp[v][u]+=w;
        }
        if(size[get(1)]!=n)puts("0");//图不连通
        else printf("%d\n",Stoer_Wagner());
    }
    return 0;
}