最小割树学习笔记

前言

最小割树（Gomory-Hu Tree）通过分治的思想，将图中的最小割关系建成一棵带权了树上问题。它的主要用途是求解全源最小割 / 最大流。

前置知识：

• 一种快速的最大流算法（Dinic/ISAP 均可，FF/EK 不行，HLPP 虽然快但不方便求最小割树），本文中采用 Dinic。
• 最小割最大流定理：最小割=最大流
• 分治思想

下文中若无例外，均用 \(O(\text{maxflow}(n,m))\) 表示求一个 \(n\) 个点 \(m\) 条边的图上任意两点之间的最大流 / 最小割的时间复杂度。

建立

首先我们将全图看成一个集合。然后我们任选两个点 \(s,t\) 跑一遍最大流。

然后你会发现，我们可以通过源点是否与其连通分成两个集合一条权为最大流流量的边。

然后将两个集合分治，重复上述操作，直到只剩下一个点为止。

这样子我们就建出了一个最小割树（因为本来一个节点的所有子树就互不连通，所以这一定是一棵树）。

（但是我们一般都不把这棵树真的建出来，为什么呢，请看下文）。

性质

最小割树的重要性质：任意两个点的最小割等于这两个点在最小割树上的路径上的最小值。

为什么呢？因为我们的最小割树的最小割和原来的图的最小割是等价的（因为我们建树的时候就是按照最小割性质建的）而树上最小割显然是路径最小值。

于是读者可能会考虑使用 倍增 / 树链剖分去解决。但是由于最大流复杂度本身过大，因此我们甚至可以暴力算出全源最小割，最后 \(O(1)\) 回答询问。

具体来说，分治时跨集合的两个点 \(u,v\) 的最小割 \(i(u,v)\) （也就是路径最小值）可以在心中脑补出来。它只和三部分有关：\(u\to s,s\to t,t\to v\)（出来，跨子树代价，进去）。我们对这三部分的最小割取最小值即可。

代码实现

重要的事情说三遍：注意退流！注意退流！注意退流！。

void GomoryHu(int l,int r){
	if(l==r) return;
	S=node[l],T=node[l+1];
	int t=maxflow(),ss=node[l],tt=node[l+1];
	ans[S][T]=ans[T][S]=t;
	int ltot=0,rtot=0;
	for(int i=l;i<=r;i++){
		if(dep[node[i]]) tl[++ltot]=node[i];
		else tr[++rtot]=node[i];
	}
	for(int i=1;i<=ltot;i++) node[i+l-1]=tl[i];
	for(int i=1;i<=rtot;i++) node[ltot+l+i-1]=tr[i];
	GomoryHu(l,l+ltot-1);
	GomoryHu(l+ltot,r);
	for(int i=1;i<=ltot;i++){
		for(int j=1;j<=rtot;j++){
			int ii=node[i+l-1],jj=node[j+ltot+l-1];
			ans[ii][jj]=ans[jj][ii]=min(min(ans[ii][ss],ans[ss][tt]),ans[tt][jj]);
		}
	}
}

课后习题

P4897 【模板】最小割树（Gomory-Hu Tree）

给出 \(n+1\) 个点和 \(m\) 条边的 无向图，\(Q\) 组询问，每组询问给出两个点，求两点之间的最小割。

\(1 \leq n \leq 500,1 \leq m \leq 1500,1 \leq Q \leq 10^5\)

P3329 [ZJOI2011]最小割

\(T\) 组数据，每组数据给出 \(n\) 个点和 \(m\) 条边的有向图，\(q\) 组询问，每组询问一个 \(x\)，求出有多少对点满足最小割小于等于 \(x\)。在两组测试数据之间需要输出一行空行。

\(1 \leq T \leq 10\)，\(1 \leq n \leq 150\)，\(0 \leq m \leq 3000\)，\(0 \leq x \leq 2^{31}-1\)，\(0 \leq q \leq 30\)

P4123 [CQOI2016]不同的最小割

给出 \(N\) 个点 \(M\) 条边的有向图，求任意两点的最小割有多少种。

\(1\leq N\leq 850,1\leq M\leq 8500\)