Gusfield

算法详解 等价流树正如其名，树上两点间的路径上的边权最小值为图上两点间的最小割。 Gusfield算法就是建等价流树的一种算法。设当前正在处理的集合为 $S(|S|\ge 2)$，从 $S$ 中任选两个点 $x,y$，求出 $x,y$ 间的最小割也就是最大流 $flow$，此时在最小割树中加入一条从 ......

算法详解 感觉最小割树是个很神奇的东西。 最小割树有一个性质：原图上的两点间的最小割大小和方案正好有一种是树上对应两点间的最小割大小和方案。 那么怎么建出这样的树呢？可以用到Gomory-Hu Tree。但我们通常只需要用到大小，这时候我们可以建出等价流树。 Gusfield算法就是建等价流树的一种 ......