图的全局最小割的Stoer-Wagner算法及例题

Stoer-Wagner算法基本思想：如果能求出图中某两个顶点之间的最小割，更新答案后合并这两个顶点继续求最小割，到最后就得到答案。

算法步骤：

-------------------------------------------------------------------------------------------------------------------------

（1）首先初始化，设最小割ans = INF                                                                                                                       |

（2）任选一个顶点u加入集合S，定义W(S,p)为S中的所有点到S外一点p的权值总和                                                            |

（3）根据选定的u更新W(S,p)的值                                                                                                                            |

（4）选出W(S,p)中值最大的点作为新的S,若S=G(V)，则继续步骤（3）                                                                          |

（5）最后进入S的两点s,t，用W(S,t)更新ans的值                                                                                                        |

（6）新建顶点c,边权w(c,v) = w(s,v)+w(t,v),删除顶点s,t及其相连的边                                                                         |

（7）若|V| > 1，则继续步骤（2）                                                                                                                            |

-------------------------------------------------------------------------------------------------------------------------

步骤（2）-（5）就是找出两个顶点，并求出它们的最小割W(S,t)，步骤（6）是删除这两个顶点，重复操作，直至顶点数变为1

复杂度：O(n^3)

例题： POJ 2914 Minimum Cut

裸的最小割

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define Mod 1000000007

using namespace std;

#define N 506

int dis[N],node[N];

int ans;

int mp[N][N];

int vis[N];

int Sto_Wag(int n)

{

    int maxi,pre,m;

    int i,j;

    for(i=;i<=n;i++)

        node[i] = i;

    while(n > )

    {

        m = -,maxi = ;

        for(i=;i<=n;i++)

        {

            dis[node[i]] = mp[node[]][node[i]];

            vis[node[i]] = ;

            if(dis[node[i]] > m)

            {

                m = dis[node[i]];

                maxi = i;

            }

        }

        pre = ;

        vis[node[]] = ;

        for(j=;j<=n;j++)

        {

            vis[node[maxi]] = ;

            if(j == n)

            {

                ans = min(ans,m);

                for(i=;i<=n;i++)

                {

                    mp[node[pre]][node[i]] += mp[node[maxi]][node[i]];

                    mp[node[i]][node[pre]] += mp[node[maxi]][node[i]];

                }

                node[maxi] = node[n--];

            }

            else

            {

                pre = maxi;

                m = -;

                for(i=;i<=n;i++)

                {

                    if(!vis[node[i]])

                    {

                        dis[node[i]] += mp[node[pre]][node[i]];

                        if(dis[node[i]] > m)

                        {

                            m = dis[node[i]];

                            maxi = i;

                        }

                    }

                }

            }

        }

    }

    return ;

}

int main()

{

    int n,m,u,v,w;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        ans = Mod;

        memset(mp,,sizeof(mp));

        while(m--)

        {

            scanf("%d%d%d",&u,&v,&w);

            u++,v++;

            mp[u][v] += w;

            mp[v][u] += w;

        }

        Sto_Wag(n);

        printf("%d\n",ans);

    }

    return ;

}