求解无向图的最小分割/整体最小划分

无向图的割:

无向图，去掉一个边集可以使图变成两个连通分量，则这个边集就是割集

无向图最小割：

边权和最小的割集。

StoerWagner算法：资料 (但是这人的代码耗时太长)

---

poj2914 Minimum Cut

类似题：hdu3002

题意：

给无向图，求全局最小割

思路：

模板题

code:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxm=505;
const int inf=1e9;
int g[maxm][maxm];
int v[maxm];//v[i]表示i合并到的顶点
int dis[maxm];//dis表示该点与A集合中所有点之间的边的长度之和
bool mark[maxm];//标记已经合并到集合里的数
int n,m;
int sw(){
    int res=inf;
    for(int i=0;i<n;i++){//开始把合并的顶点设置成自己
        v[i]=i;
    }
    while(n>1){
        int pre=0;//pre表示之前加入A集合的点，以0点为第一个加入A集合的点
        memset(mark,0,sizeof mark);
        memset(dis,0,sizeof dis);
        for(int i=1;i<n;i++){
            int k=-1;
            for(int j=1;j<n;j++){
                if(!mark[v[j]]){
                    dis[v[j]]+=g[v[pre]][v[j]];
                    if(k==-1||dis[v[k]]<dis[v[j]]){
                        k=j;
                    }
                }
            }
            mark[v[k]]=1;
            if(i==n-1){
                res=min(res,dis[v[k]]);
                for(int j=0;j<n;j++){
                    g[v[j]][v[pre]]=g[v[pre]][v[j]]+=g[v[j]][v[k]];
                }
                v[k]=v[--n];
            }
            pre=k;
        }
    }
    return res;
}
signed main(){
    while(scanf("%d%d",&n,&m)!=EOF){
   		memset(g,0,sizeof g);
        for(int i=1;i<=m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            g[a][b]=g[b][a]+=c;
        }
        printf("%d\n",sw());
    }
    return 0;
}

---

hdu3691 Nubulsa Expo

题意：

无向图，给起点，你可以任意指定一个终点，使得这两个点之间的最大流最大，求这个最大流。

思路:

由最大流最小割定理，题目变成任意指定一个终点，使得起点和终点之间的割最小，求这个割。
因为不管最小割如何，起点必然在一个集合，只要随意在另一个集合找一个终点，即可得到所求最小割，所以题目就变为求全局最小割。

code:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxm=505;
const int inf=1e9;
int g[maxm][maxm];
int v[maxm];//v[i]表示i合并到的顶点
int dis[maxm];//dis表示该点与A集合中所有点之间的边的长度之和
bool mark[maxm];//标记已经合并到集合里的数
int n,m,s;
int sw(){
    int res=inf;
    for(int i=0;i<n;i++){//初始还未合并，都代表节点本身
        v[i]=i;
    }
    while(n>1){
        int pre=0;//pre表示之前加入A集合的点，以0点为第一个加入A集合的点
        for(int i=0;i<n;i++){
            mark[v[i]]=0;//切记里面是v[i]不是i
            dis[v[i]]=0;
        }
        for(int i=1;i<n;i++){//求出某轮最大生成树的最后两个节点，并且去除最后的t，将与t连接的边归并
            int k=-1;
            for(int j=1;j<n;j++){
                if(!mark[v[j]]){
                    dis[v[j]]+=g[v[j]][v[pre]];//j到A集合的距离增加
                    if(k==-1||dis[v[k]]<dis[v[j]]){//找出dis最大的点k(外面再开一个for耗时会增大)
                        k=j;
                    }
                }
            }
            mark[v[k]]=1;//标记点k为已经加入A集合
            if(i==n-1){//若|A|=|V|(所有点都加入了A),结束
                res=min(res,dis[v[k]]);
                for(int j=0;j<n;j++){
                    g[v[j]][v[pre]]=g[v[pre]][v[j]]+=g[v[j]][v[k]];
                }
                v[k]=v[--n];//删除最后一个点(删除t,即t合并到s)
            }
            pre=k;//更新pre
        }
    }
    return res;//返回最小割
}
signed main(){
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
        if(!(n+m+s))break;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                g[i][j]=0;
            }
        }
        for(int i=1;i<=m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--,b--;//改成下标从0开始
            g[a][b]=g[b][a]+=c;
        }
        printf("%d\n",sw());
    }
    return 0;
}

---