题解：CF1095F Make It Connected （不一样的做法）

Carey_chen · 2026-08-07 15:27:13 · 题解

这是一个双 \log 的 Kruscal 做法。

我们不能一次性加入所有边，考虑使用优先队列动态的模拟 Kruscal 选边的过程。

先将优惠边全部加入队列中。

之后，我们先把以每一个节点为起点的最短非优惠边加入队列，每次使用一条非优惠边后，再加入下一条最短的边。

对 a 从小到大排序，对于每个点 u，我们按编号顺序选择一个 v(v>u)，使得 u 和 v 不在同一连通块，且边权 a_u+a_v 最小，把边 (u,v) 加入优先队列中。

然而这样还是 O(n^2) 的，因为下一条端点不连通的非优惠边可能非常远。我们需要优化选边的过程。

考虑使用 STL 维护更多信息，对每个连通块维护一个 map，表示该连通块内节点的编号连续段。加入新边时，我们只需在 map 中找到第一个右端点不小于 u 的区间即可。

参考颜色段均摊的时间复杂度证明，再结合 map 的复杂度，我们可以知道，所有查询的均摊复杂度为 O(\log^2 n)。

合并两个集合时，我们采用启发式合并。

总复杂度为 O((n+m)\log (n+m)+n\log^2 n)。可以在 CF 上通过。