2013-team4/code/stoer-wagner

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
给出一个无向图，求移除权值最少的边使得这个图被分为两个连通块。
Stoer-Wagner算法：时间复杂度O(N^3)，空间复杂度O(N^2)
算法步骤：利用了Prim的贪心思想，每次加入最长路径的点，我们定义W(A, p)为A中的所有点到集合A外一点p的权值的和，设无向图为G(V,E)：
①初始化最小割min_cut=+∞；
②集合A={a}，a为V中任意顶点；
③更新W(A,x)，选取V-A中的W(A, x)最大的点x加入集合A，重复前面直到|A|=|V|。设倒数第二个加入A的点为s，添加s后的集合A设为集合B，最后一个加入A的点为t；
④更新min_cut=min(min_cut,W(B,t))；
⑤新建顶点c, 添加到V，权值w(c,v)=w(v,c)=w(s,v)+w(t,v), 删除顶点s和t, 以及与这两点相连的边；
⑥如果此时|V|>1则转②；
}}}
{{{
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN=500+10;
const int inf=1000000000;

int map[MAXN][MAXN], dis[MAXN], ver[MAXN];
bool vis[MAXN];
int n, m;

int stoer_wagner(int n) {
    int i, j, ret=inf;
    for (i=0; i<n; i++) ver[i]=i;
    while (n>1) {
        int t=1, s=0;
        for (i=1; i<n; i++) {
            dis[ver[i]]=map[ver[0]][ver[i]];
            if (dis[ver[i]]>dis[ver[t]]) t=i;
        }
        memset(vis, 0, sizeof(vis)); vis[0]=true;
        for (i=1; i<n; i++) {
            if (i==n-1) {
                ret=min(ret, dis[ver[t]]);
                for (j=0; j<n; j++) {
                    map[ver[s]][ver[j]]+=map[ver[j]][ver[t]];
                    map[ver[j]][ver[s]]+=map[ver[j]][ver[t]];
                }
                ver[t]=ver[--n];
            }
            vis[ver[t]]=true; s=t; t=-1;
            for (j=1; j<n; j++)
                if (!vis[ver[j]]) {
                    dis[ver[j]]+=map[ver[s]][ver[j]];
                    if (t==-1||dis[ver[t]]<dis[ver[j]]) t=j;
                }
        }
    }
    return ret;
}

int main() {
    while (scanf("%d%d", &n, &m)==2) {
        memset(map, 0, sizeof(map));
        for (int u, v, w, i=0; i<m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            map[u][v]+=w; map[v][u]+=w;
        }
        printf("%d\n", stoer_wagner(n));
    }
    return 0;
}
}}}

给出一个无向图，求移除权值最少的边使得这个图被分为两个连通块。
Stoer-Wagner算法：时间复杂度O(N^3)，空间复杂度O(N^2)
算法步骤：利用了Prim的贪心思想，每次加入最长路径的点，我们定义W(A, p)为A中的所有点到集合A外一点p的权值的和，设无向图为G(V,E)：
①初始化最小割min_cut=+∞；
②集合A={a}，a为V中任意顶点；
③更新W(A,x)，选取V-A中的W(A, x)最大的点x加入集合A，重复前面直到|A|=|V|。设倒数第二个加入A的点为s，添加s后的集合A设为集合B，最后一个加入A的点为t；
④更新min_cut=min(min_cut,W(B,t))；
⑤新建顶点c, 添加到V，权值w(c,v)=w(v,c)=w(s,v)+w(t,v), 删除顶点s和t, 以及与这两点相连的边；
⑥如果此时|V|>1则转②；

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=500+10;
const int inf=1000000000;
int map[MAXN][MAXN], dis[MAXN], ver[MAXN];
bool vis[MAXN];
int n, m;
int stoer_wagner(int n) {
    int i, j, ret=inf;
    for (i=0; i<n; i++) ver[i]=i;
    while (n>1) {
        int t=1, s=0;
        for (i=1; i<n; i++) {
            dis[ver[i]]=map[ver[0]][ver[i]];
            if (dis[ver[i]]>dis[ver[t]]) t=i;
        }
        memset(vis, 0, sizeof(vis)); vis[0]=true;
        for (i=1; i<n; i++) {
            if (i==n-1) {
                ret=min(ret, dis[ver[t]]);
                for (j=0; j<n; j++) {
                    map[ver[s]][ver[j]]+=map[ver[j]][ver[t]];
                    map[ver[j]][ver[s]]+=map[ver[j]][ver[t]];
                }
                ver[t]=ver[--n];
            }
            vis[ver[t]]=true; s=t; t=-1;
            for (j=1; j<n; j++)
                if (!vis[ver[j]]) {
                    dis[ver[j]]+=map[ver[s]][ver[j]];
                    if (t==-1||dis[ver[t]]<dis[ver[j]]) t=j;
                }
        }
    }
    return ret;
}
int main() {
    while (scanf("%d%d", &n, &m)==2) {
        memset(map, 0, sizeof(map));
        for (int u, v, w, i=0; i<m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            map[u][v]+=w; map[v][u]+=w;
        }
        printf("%d\n", stoer_wagner(n));
    }
    return 0;
}