P1967 [NOIP2013 提高组] 货车运输 分析

__ryp__ · 2024-02-01 21:14:46 · 个人记录

其实就是找 x 到 y 上的边权最小值的最大值。

那么我们可以考虑建一个最大生成树，然后在上面用倍增（LCA）来取边权的最小值。容易证明，在这个最大生成树上的边权最小值，一定是可能的最大值。

建最大生成树的过程实际上和最小生成树的贪心策略是一样的（Kruskal），只是排序反过来。

LCA 的特殊之处在于需要维护一个最小值的倍增。

别的就是板子了。以上。