Kruskal 重构树

简述

Kruskal 重构树是图的一种生成树,主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质,所以很容易就可以解决边权的取值限制。

建法

Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似,但是结构有所不同:Kruskal 重构树将边权变成点权,点权依深度变小。我们假设有一张这样的图:

继续阅读Kruskal 重构树