P4047 [JSOI2010] 部落划分 分析

__ryp__ · 2023-12-14 13:04:04 · 个人记录

乍看本题以为是二分，但正解实际上是 MST。

“部落” 实际上就是连通块，而本题所要求的就是让连通块之间的路径最大（两个最近的部落之间尽可能远离）。

我们可以求这个图的最小生成树，这样，这棵 MST 中前 k 大的边就是所要断开的部落之间的路径。所以，这前 k 大的边中最小的也就是整个 MST 的边中的第 k - 1 大的边。

在 Prim 中维护所生成的 MST，最后输出第 k - 1 大即可。