算法

最小割树是一个用于快速求无向图上任意两点间最小割的算法，它的定义如下：

称树 $T$ 为 无向图 $G$ 的最小割树，当且仅当 $T$ 的节点与 $G$ 一一对应，且对于所有边 $(u,v)\in T$，其边权为原图中 $u,v$ 两点间最小割，同时满足在 $T$ 中去掉这条边后剩下的两个不连通点集恰好为原图中 $u,v$ 的最小割将原图分为的两个点集。

显然，我们可以直接根据定义递归建树，并利用最小割最大流定理每次跑一边网络流，代码：

void build(int l,int r){//node[l]到node[r]为当前要处理的连通点集 if(l == r) return; int u = node[l],v = node[l + 1];//任选两点 add(u,v,Max_Flow:: Dinic(u,v)); int t1 = l - 1,t2 = r + 1; for(int i = l; i <= r; i ++){ if(Max_Flow:: d[node[i]] == -1) t[--t2] = node[i]; else t[++t1] = node[i]; //d为Dinic的bfs中的到达数组，显然此时d中存的是最后一次bfs时的残量网络的连通情况 //因为现在残量网络上s到达不了t,所以bfs访问到的点就是s所在的点集，它们的d不为0 } for(int i = l; i <= r; i ++) node[i] = t[i]; build(l,t1),build(t2,r);//node[l]到node[t1]为u所在点集，node[t2]~node[r]为v所在点集 }

那建出树后怎么查询呢？最小割树有一个重要的性质：

对于原图中任意两点 $u,v$，其最小割等于树上两点路径上边权的最小值

所以直接倍增维护就可以了。

证明

其正确性证明可以去看这篇博客，写的很严谨。

关于时间复杂度

严格来说，其时间复杂度上界约为 $\mathrm{O}(n^{3}m)$（共跑 $n-1$ 次最大流）。

但众所周知，网络流尤其是 Dinic / ISAP 的时间复杂度几乎不可能被卡满，更别说是在同一图中每次随机选两个点了，所以这个算法实际上跑的飞快。在 $n⩽850,m⩽8500$ 且不开 O2 的情况下，最大点依旧只有 $1.02\mathrm{s}$（甚至没用 ISAP，只是 Dinic 加两个常见优化） 。所以在需要用的时候尽管用，不需要算复杂度。

上面那题开了 O2 甚至可以不用 ISAP 卡到恐怖的总用时$\sout{240\mathrm{m}\mathrm{s}}$

代码

下面是洛谷模板题的代码

#include <iostream> #include <cstdio> #include <queue> using namespace std; const int maxn = 550,maxm = 1550,inf = 1e9; int n,m,q,x,y,z,last[maxn],d[maxn],node[maxn],t[maxn],f[maxn][10],g[maxn][10]; struct Edge{ int v,w,nxt; }e[2 * maxm]; namespace Max_Flow{//Dinic 模板 int cnt = 1,c[2 * maxm],last[maxn],d[maxn],lst[maxn]; queue <int> q; struct Edge{ int v,w,nxt; }e[2 * maxm]; inline void insert(int u,int v,int w){ cnt ++,e[cnt] = {v,w,last[u]}; last[u] = cnt,c[cnt] = w; } inline void add(int u,int v,int w){ insert(u,v,w); insert(v,u,w); //因为是无向图，可以直接把反向边初值设为流量，这样可以节省大量时间（这题单点直接快1s+） } bool bfs(int S,int T){ for(int i = 1; i <= n; i ++) d[i] = -1,lst[i] = last[i]; q.push(S),d[S] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = last[u]; i; i = e[i].nxt){ int v = e[i].v; if(e[i].w && d[v] == -1){ d[v] = d[u] + 1; q.push(v); } } } return d[T] != -1; } int dfs(int u,int k,int T){//当前弧优化 + 剪枝 if(u == T) return k; int s = 0; for(int i = lst[u]; i && k; i = e[i].nxt){ lst[u] = i; int v = e[i].v; if(d[v] == d[u] + 1 && e[i].w){ int t = dfs(v,min(k,e[i].w),T); e[i].w -= t,e[i ^ 1].w += t,s += t,k -= t; } } if(s == 0) d[u] = 0;//流量为0时直接标记，但注意不能置为-1，因为建树时要区分点集 return s; } inline void init(){ for(int i = 1; i <= cnt; i ++) e[i].w = c[i]; } int Dinic(int S,int T){ init(); int sum = 0; while(bfs(S,T)) sum += dfs(S,inf,T); return sum; } } int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + (c ^ 48),c = getchar(); return x; } inline void insert(int u,int v,int w){ static int cnt = 0; e[++cnt] = {v,w,last[u]},last[u] = cnt; } inline void add(int u,int v,int w){ insert(u,v,w); insert(v,u,w); } void build(int l,int r){ if(l == r) return; int u = node[l],v = node[l + 1]; add(u,v,Max_Flow:: Dinic(u,v)); int t1 = l - 1,t2 = r + 1; for(int i = l; i <= r; i ++){ if(Max_Flow:: d[node[i]] == -1) t[--t2] = node[i]; else t[++t1] = node[i]; } for(int i = l; i <= r; i ++) node[i] = t[i]; build(l,t1),build(t2,r); } void dfs(int u,int fa){//倍增随便维护 d[u] = d[fa] + 1; for(int i = 1; g[u][i - 1]; i ++) g[u][i] = g[g[u][i - 1]][i - 1],f[u][i] = min(f[u][i - 1],f[g[u][i - 1]][i - 1]); for(int i = last[u]; i; i = e[i].nxt){ int v = e[i].v; if(v == fa) continue; f[v][0] = e[i].w,g[v][0] = u; dfs(v,u); } } int solve(int u,int v){ int ret = inf; if(d[u] < d[v]) swap(u,v); for(int i = 8; i >= 0; i --) if(d[g[u][i]] >= d[v]) ret = min(ret,f[u][i]),u = g[u][i]; if(u == v) return ret; for(int i = 8; i >= 0; i --) if(g[u][i] != g[v][i]) ret = min(ret,min(f[u][i],f[v][i])),u = g[u][i],v = g[v][i]; return min(ret,min(f[u][0],f[v][0])); } int main(){ // freopen("data.txt","r",stdin); n = read(),m = read(); for(int i = 1; i <= m; i ++){ x = read(),y = read(),z = read(); Max_Flow:: add(x,y,z); } for(int i = 1; i <= n; i ++) node[i] = i; build(1,n); for(int i = 1; i <= n; i ++) for(int j = 0; j <= 8; j ++) f[i][j] = inf; dfs(1,0); q = read(); while(q --){ x = read(),y = read(); printf("%d\n",solve(x,y)); } return 0; }

你可能会注意到没有例题，因为目前关于最小割树的题好像都是板子。。。