[文章目录]
Description
有一个n个点，m条边的无向图，求将这个图断成两个联通块需要删除的边的边权和最小值。n<=500 m<=10000
Stoer Wagner 算法，求图的全局最小割，时间复杂O(n^3)
就是维护一个集合，每次向里扔不在当前集合的点中与当前集合联通性最强的点，用最后一个点与当前集合之间的联通性更新答案，然后将后两个进入集合的点缩成一个点。再重复进行这个操作即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 510
const int inf=0x3f3f3f3f;
int n,m,mp[N][N];
int Stoer_Wagner()
{
static int f[N],z[N];
static bool v[N],del[N];
int re=inf,t,i,j,k,top;
for(t=n;t>1;--t)
{
memset(f,0,sizeof f);
memset(v,0,sizeof v);
top=0,f[0]=-1;
for(i=1;i<=t;++i)
{
for(k=0,j=1;j<=n;++j) if(!del[j]&&!v[j]&&f[j]>f[k]) k=j;
z[++top]=k; v[k]=1;
for(j=1;j<=n;++j) if(!del[j]&&!v[j]) f[j]+=mp[k][j];
}
re=min(re,f[z[top]]);
for(i=1;i<=n;++i) if(!del[i])
{
if(i!=z[top]&&i!=z[top-1])
{
mp[z[top-1]][i]+=mp[z[top]][i];
mp[i][z[top-1]]+=mp[i][z[top]];
}
mp[i][z[top]]=mp[z[top]][i]=0;
}
del[z[top]]=1;
}
return re;
}
int main()
{
scanf("%d%d",&n,&m);
int i,a,b,c;
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&c);
mp[a][b]+=c; mp[b][a]+=c;
}
printf("%d",Stoer_Wagner());
return 0;
}