题意
(n) 个点 (m) 条边的无向带权图求全局最小割。(nle 500,mle frac{n(n-1)}{2}) 。
分析
参考了 这篇博客，去给他点赞。
嘛，今天研究了一下全局最小割。
全局最小割是什么呀？
运用经典的最大流最小割，我们可以在网络流复杂度内求出对于两个点 (s,t) ，把图分成 (sin S) 集和 (tin T) 集的需要去掉的最小边权和。我们称这种割为对于一组点 ((s,t)) 的 (s-t) 割。
全局最小割，就是把整个无向图割开，却不指定怎么割，求最小边权和。
用之前的方法，(O(n*网络流)) 可以分治得到最小割树，从而求出任意两点间的最小割，那么取最小边权就是答案。但已知理论复杂度比较优秀的网络流算法复杂度也达到 (O(n^2sqrt m)) （最高标号预留推进），再乘上 (n) ，这是一个很高的复杂度。
是否有办法优化呢？这个问题中 不指定要割什么 这个条件并没有用上，可以从这里入手。
下面就来介绍全局最小割的 Stoer-Wagner 算法。
整体思路
解决这个问题，有一个关键的性质需要利用。
设 (s,t) 为图中两点，那么在任意一个割中，它们要么在同一个集合中，要么在不同的集合中。
算法的整体思路是，我们不指定割开哪两个点，而是设计一个函数 (f(G)) ，返回一个三元组 ((s,t,c)) ，表示这个图中 ((s,t)) 的最小割为 (c) 。注意，这个函数告诉我们它割开哪两个点，而不是我们告诉它 。利用上面的性质，要么这个图的全局最小割要么就是 (c) ，要么 (s,t) 在同一集合中。
为什么是这样呢？显然图的全局最小割一定小于等于 (c) ，若全局最小割下 (s,t) 在不同集合中，而全局最小割却小于 (c) ，那么必然存在更小的 (s-t) 割，这与 (c) 是 (s-t) 最小割矛盾。
我们把答案对 (c) 取 (min)，接下来就讨论 (s,t) 在同一集合中的情况。若是这样，那么其实可以把 (s,t) 并起来，因为 (s) 与 (t) 中间的边是不会割掉的。所以就把 (s,t) 并起来，把边合并就好啦！
这样进行，直到图中只剩下一个点，我们就得到了答案。显然上面的过程进行了 (n-1) 次，所以复杂度为 (O(n(m+f))) 。接下来只要我们能够有一个函数，快速地告诉我们一对点间的最小割，问题就解决啦。
函数 (f(G))
算法流程
- 有一个空集 (A) ，最开始在 (G) 中任意找一个点放进 (A) 。
- 不断在 (G) 中找到一个点 (v otin A) 使得它到 (A) 中所有连边权值和最大，把这个点加入 (A) ，直到 (A=V) 。
- 倒数第二个加入 (A) 和最后加入 (A) 的两点即分别为 (s,t) ，它们的最小割是 (t) 到 (V-lbrace t brace) 的边权和。
下面证明这个算法的正确性。实际上要说明的是，对于任意一个点集的划分 (V=S+T) 使得 (sin S,tin T) ，有 (cut(V-lbrace t brace,lbrace t brace)le cut(S,T)) 。
一些记号
- (w(e)) ，边 (e) 的权值；(w(x,y)) ，边 ((x,y)) 的权值
- (w(S,x)=sum _{vin S,(x,v)in E}w(x,v))
- (C) ，对于点集的划分 (S,T) 的最小割
- (a) ，加入 (A) 的点的序列，(a_i) 表示第 (i) 个加入 (A) 的点
- (A_x) ，加入 (x) 之前加入 (A) 的点的集合，不包含 (x)
- (C_x) ，(lbrace (u,v)|u,vin A_xcaplbrace x brace,(u,v)in C brace) 。此处 (C) 就是上面的那个，即 (C) 在 (A_xcap lbrace x brace) 中的诱导割。
- (Bsetminus C) ，(B) 集合中去掉集合 (C) 剩下的集合，即 (C) 在 (B) 中的补集。
接下来要证明，对于所有点 (v) 满足 (a) 中排 (v) 前面的点与 (v) 不在割 (C) 的同一侧，有 (w(A_v,v)le C_v) 。若能得到这个，由于 (t) 是满足这个条件的，就有 (w(A_t,t)=w(V-lbrace t brace,t)=cut(V-lbrace t brace,lbrace t brace)le C_t) ，即得到上面的结论。
对第一个满足条件的 (v) ，等号成立，因为 (v) 是第一个不与前面在同一集合中的点，所以 (C_v) 就是 (w(A_v,v)) ，这些边是一定要割掉的。下面对 (v) 用归纳法。
设对于一个满足条件的 (v) 以及前面满足条件的点，结论都成立，那么对于 (v) 的下一个点 (u) ，说明这个结论成立。
首先有 (w(A_u,u)=w(A_v,u)+w(A_usetminus A_v,u)) ，这是显然的，因为它是对集合 (A_u) 的一个划分。
由归纳假设可得，(w(A_v,v)le C_v) ，又因为算法过程告诉我们 (u) 在 (v) 后面加入，所以在加入 (v) 之前一刻，(v) 与 (A_v) 的连边权值和大于 (u) 与 (A_v) 连边的权值和，所以有 (w(A_v,u)le w(A_v,v)) ，于是得到：
(C_u) 的含义，是在一个 ((S,T)) 割中要把 (A_ucap lbrace u brace) 割成两部分的那部分。这一定包含了 (C_v) ，因为 (v) 与之前的那个也不再同一个集合中。(w(A_usetminus A_v,u)) 一定是要割掉的，否则就无法保证 (u) 与之前的那个不在同一集合中。于是得到：
联立上两式，得到：
这样我们证明了结论。
函数 (f) 的复杂度直接做是 (O(m+n^2)) ，可以用斐波那契堆优化到 (O(m+nlog n)) （普通堆是 (O((m+n)log n)) ，在稠密图中与 (O(m+n^2)) 没有什么区别）。因此整个算法的复杂度为 (O(nm+n^3)) 或 (O(nm+n^2log n)) 。
代码
#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
#include<algorithm>
#define M(x) memset(x,0,sizeof x)
using namespace std;
inline int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=1e3+1;
int n,m;
namespace graph {
int d[maxn],f[maxn][maxn],ed;
bool no[maxn],ina[maxn];
inline void clear() {M(no),M(f);}
inline void add(int x,int y,int w) {
f[x][y]+=w;
}
void newlink(int nw,int s,int t) {
for (int v=1;v<=ed;++v) if (!no[v] && v!=t) {
add(nw,v,f[s][v]);
add(v,nw,f[s][v]);
}
}
inline void push(int x) {
ina[x]=true;
for (int v=1;v<=ed;++v) if (!no[v] && !ina[v]) d[v]+=f[x][v];
}
int glob(int cs,int &s,int &t) {
M(d),M(ina);
int a;
for (a=1;a<=ed && (no[a] || ina[a]);++a);
push(t=a);
while (cs--) {
int p=0;
for (int i=1;i<=ed;++i) if (!no[i] && !ina[i] && d[i]>d[p]) p=i;
s=t,t=p;
push(p);
}
return d[t];
}
int run() {
int ret=INT_MAX,here=(n-1)<<1;
for (ed=n;ed<=here;++ed) {
int s=0,t=0,g=glob((n<<1)-ed-1,s,t);
ret=min(ret,g);
int nw=ed+1;
newlink(nw,s,t);
newlink(nw,t,s);
no[s]=no[t]=true;
}
return ret;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
while (~scanf("%d%d",&n,&m)) {
graph::clear();
for (int i=1;i<=m;++i) {
int x=read()+1,y=read()+1,w=read();
graph::add(x,y,w),graph::add(y,x,w);
}
int ans=graph::run();
printf("%d
",ans);
}
return 0;
}