简述
Kruskal 重构树是图的一种生成树，主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质，所以很容易就可以解决边权的取值限制。
建法
Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似，但是结构有所不同：Kruskal 重构树将边权变成点权，点权依深度变小。我们假设有一张这样的图：
P3980:「NOI2008」志愿者招募题解
解法
我们可以把整个工作流程想像成网络流上的一条链：第\(i\)天连接到第\(i+1\)天的，流量为\(INF – A_i\)，费用为\(0\)；其中第\(n+1\)连接到汇点，流量为\(INF\)，费用为\(0\)；源点连接到点\(1\)，流量为\(INF\)，费用为\(0\)。
对于每一组志愿者\((s_i, t_i, c_i)\)，考虑连边\((s_i, t_i + 1, INF, c_i)\)，这样意味着整个工作流中可以从额外管道中获取流量，将最大流调整到\(INF\)。
所以求得的最小费用肯定是在最大流量\(INF\)的前提下求得的，即为答案。
P2604:「ZJOI2010」网络扩容题解
解法
大水题。
考虑按照给定数据建一张费用全部为 0 的图。跑完费用流求最大流输出答案之后，在现有的边的基础上加一条方向一致、容量无限、费用为\(w_i\)的边，最后开一个新点连接点\(n\)，容量为\(k\)即可。