最小割树小记

最小割树是一种支持动态查询两点间最小割的结构。

构造

任意选两个点 \(s,t\)，在全图上跑出 \(s\to t\) 的最小割 \(w\)，建立边 \((s,t,w)\)。设残量网络上与 \(s\) 连通的部分为 \(S\)，与 \(t\) 连通的部分为 \(T\)，则将图分成 \(S,T\) 两个点集，并在两个点集上做类似的事情，直到点集只剩下一个点。

此时 \(u,v\) 的最小割为树上路径最小值。

证明

引理 \(1\)：若 \(u,v\) 分别在 \(S,T\) 内，则 \(\text{cut}(u,v)\leq \text{cut}(s,t)\)。

容易发现 \(s\to t\) 的割事实上构造了 \(u\to v\) 的割的上界。

引理 \(2\)：任意选三个点 \(a,b,c\)，则 \(|\{\text{cut}(a,b),\text{cut}(b,c),\text{cut}(a,c)\}|\leq 2\)。

若三个互不相同，则取最大的，不妨设为 \(\text{cut}(a,b)\)，则 \(a,b\) 在 \(\text{cut}(a,c),\text{cut}(b,c)\) 必然位于同侧，那么后两者显然相同，否则可以调整。

推论：\(\text{cut}(a,b)\geq\min(\text{a,c},\text{b,c})\)。多元情况：\(\text{cut}(x_1,x_k)\geq \min_{i=1}^k\text{cut}(x_i,x_{i+1})\)。

回到原问题，取路径上两点 \(u,v\)，考察最小的边 \((x,y)\)，显然 \(u,v\) 位于 \(x,y\) 最小割异侧，故 \(\text{cut}(u,v)\leq\text{cut}(x,y)\)，根据推论有 \(\text{cut}(u,v)\geq \text{cut}(x,y)\)，QED。

本质地，最小割树依赖于一个事实：在某次最小割之后，处于残量网络上同一连通块的两点之间最小割必定位于这个连通块内部，而这构成了一个树的结构。