Stoer-Wagner算法

$Stoer-Wagner$ 算法

传送门

我们的处理方法是权值将权值大的边的两个点放入一个联通块，因为这条边几乎不太可能被“割”，每回最后剩下的点是可能要“割”的点。

我们每次“并”掉一个点（就是上面所说的剩的点，不是“割”掉，不能保证最优）后，要对于“并入”的那个点的边要进行权值的累计（最后要统计权值，不能平白无故的让边的权值“消失”）。

没有直接割点的原因是不能保证最优，为什么呢？

假设有一张图：$a,b,c$ 三个节点，$a\rightarrow b$ 的权值是 $4$，$b\rightarrow a$ 的权值是 $4$，$b\rightarrow c$ 的权值是 $7$。

根据最小割的定义，最后的结果是 $7$，但是如果我们一开始就将割最大边 $7$ 视为不能事件，那么答案一定不正确。

所以对于每次选择要“并”的点，要更新边权，找到真正的最小割。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  return k*f;
} 
const int o_o=610;
const int m_a=1e9;
int s,t;
int m_p[o_o][o_o];//两点间的距离 
int v_l[o_o];//记录到当前节点的权值 
int b_p[o_o];//标记点是否被扔掉 
int b_b[o_o];//记录标记 
int i_d[o_o];//记录顺序 
int n,m;
int p_r(int x){
  //初始化 
  memset(b_b,0,sizeof(b_b));//清空标记 
  memset(v_l,0,sizeof(v_l));//清空权值 
  v_l[0]=-1;
  
  //尽量把权值大的边的点标记，不会对最小割有影响 
  for(int i=1;i<=x+1;i++){//枚举剩余点 
    int k_k=0;
    for(int j=1;j<=n;j++)//枚举所有点 
      if(!b_p[j]&&!b_b[j]&&v_l[j]>v_l[k_k])k_k=j;//找权值最大 
    b_b[k_k]=1;//标记（以后不会再选了） 
    i_d[i]=k_k;//记录第 i 次“使用”的点 
    for(int j=1;j<=n;j++)//所有和它有连边的点累计权值 
      if(!b_p[j]&&!b_b[j])v_l[j]+=m_p[k_k][j];
  }
  
  //要处理的点 
  s=i_d[x];//要“加”点的点 
  t=i_d[x+1];//要被并入的点 
  return v_l[t];//最小点的权值 
}
int g_a(){
  int r_s=m_a;//初始化为最大值 
  //最后只剩一个点 
  for(int i=n-1;i>=1;i--){
    //枚举的点不断减少，不断有点被踢出 
    r_s=min(r_s,p_r(i));//取最小值 
    b_p[t]=1;//标记已经被踢掉 
    for(int j=1;j<=n;j++){//“加”点边更新 
      //m_p[a][b]=m_p[b][a] 
      m_p[s][j]+=m_p[t][j]; 
      m_p[j][s]+=m_p[j][t];
    }
  }
  return r_s;
}
int main(){
  n=r_r(),m=r_r();
  for(int i=1;i<=m;i++){//加边 
    int x=r_r(),y=r_r(),v=r_r();
    m_p[x][y]+=v;
    m_p[y][x]+=v;
  }
  printf("%d\n",g_a());
  return 0;
}