刚才可能是有用算法。这次是无用算法。
无向图的最小割是最小的边集使得割掉后不连通。Stoer-Wagner 算法可以在 \(O(n^3)\) 复杂度内解决无向图最小割。或者说实际上是 \(O(nm\log m)\)。
首先有一句废话：对于任意两点 \(s,t\) ,割掉最小割后，或者处于一个连通块，或者处于不同的两个连通块。
那么考虑如何处理这两种。对于同一连通块的情况，显然可以把 \(s,t\) 缩成一个点，然后把所有连出去的边的边权变成连到两个点的边权和。于是我们只要求 \(n-1\) 次两点间的最小割，每处理一次缩一个点。
于是考虑如何处理 \(s,t\) 间的最小割。显然不是网络流。
构造过程是这样的：设 \(w_i\) 为点 \(i\) 连出去的所有边的边权和。构造一个集合 \(A\) 初始为空，每次选 \(w_i\) 最大的一个加入 \(A\) 中，那么最后加入的两个点的最小割就是最后加入的点的权值。懒得证明。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,m,S,T,a[610][610],w[610],ord[610];
bool vis[610],v[610];
int solve(int x){
memset(w,0,sizeof(w));
memset(vis,0,sizeof(vis));
w[0]=-1;
for(int i=1;i<=n-x+1;i++){
int mx=0;
for(int j=1;j<=n;j++){
if(!v[j]&&!vis[j]&&w[j]>w[mx])mx=j;
}
vis[mx]=true;ord[i]=mx;
for(int j=1;j<=n;j++){
if(!v[j]&&!vis[j])w[j]+=a[mx][j];
}
}
S=ord[n-x],T=ord[n-x+1];
return w[T];
}
int sw(){
int ans=0x3f3f3f3f;
for(int i=1;i<n;i++){
ans=min(ans,solve(i));
v[T]=1;
for(int j=1;j<=n;j++){
a[S][j]+=a[T][j];a[j][S]+=a[j][T];
}
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
a[u][v]+=w;a[v][u]+=w;
}
printf("%d\n",sw());
return 0;
}