图论、网络流：最小割树 (Gomory-Hu Tree)

Gomory-Hu Tree

以下分析约定：

符号	含义
$val_S$	令 $S$ 是边集，那么 $c(S)$ 就是其边权和
$cut_{u,v}=\{U,V-U\}$	分割 $u,v$ 的最小割，其中 $u\in U, v\in V-U$
$edge_U$	对于一个割 $U,V-U$，其为割下的所有边，即 $\{(u,v):u\in U,v\in V-U\}$
$mincut_{u,v}$	$(u,v)$ 的最小割（权值最小）
$minval_{u,v}$	$=val(mincut(u,v))$

最小割树 $T=(V,E_T)$ 是这样一种树，对于所有的边 $(s,t)\in E_T$，从树上去掉这两条边之后剩下的两个连通块 $S,T$，恰好就是 $s,t$ 的最小割 $mincut_{s,t}$

代码实现

1

// pass

例题