AT_cf17_final_j Tree MST 题解

ZnPdCo · 2025-10-11 20:48:25 · 题解

怎么没有简单好写还是线性的做法。

如果你做题量过万，肯定做过 Yet Another MST Problem：

给你一个 n 个点 m 条边的无向连通图 G，给定关键点集合 S。有一个点集是 S 的有权无向完全图 H，其中两点 u,v 之间的距离是两个点在 G 上的最短距离。求 H 的最小生成树。

原题的做法是将关键点塞入队列跑多源 bfs，每个点记录它到哪个关键点距离最短，距离最短是多少。对于每条边 (u,v,w)，如果它两端的最近的关键点 s,t 是不同的，那么我们就将 (s,t,dis(u,s)+dis(v,t)+w) 加入可能的边集 E。最后把 E 排序跑 Kruskal 即可。复杂度是 O(n(\log n+\alpha(n))) 的。

算法的正确性可以口胡一下，因为两个不同的关键点 p 到 q 的路径上一定会存在一条边两端连接的关键点不同，所以我们只需要记录所有边就好了。

相信你已经会做这道题了：

对每个点 i 建一个虚点 i+n，连边权为 x_i 的边，将虚点作为关键点跑上述算法即可。只需要将多源 bfs 替换为多源 dijkstra 即可。

参考实现复杂度依旧是 O(n(\log n+\alpha(n))) 的。

然后我们发现跑 dijkstra 的是一个树，所以其实我们可以直接跑两次 dfs，一次向上更新，一次向下更新，求出最短距离。

同时，我们发现其实满足「两端的最近关键点不同」的边有且仅有 n-1 条。

这是因为我们将「最近关键点」看作颜色，相当于每个点有 n 种颜色，而且每种颜色至少出现一次，并且相同颜色的点集是联通的。

可以证明有且仅有 n-1 条连接两个不同颜色的边，具体证明可以考虑缩点。

因为只有 n-1 条，所以所有边都在 MST 上。我们将所有满足「两端的最近关键点不同」的边的贡献直接加到答案里就对了，不需要跑 Kruskal，需要注意的是，计算「最近关键点」的算法实现不能太随意，需要使得相同颜色的点集是联通的。

参考实现里没有显式建出关键点，不过是类似的，只需要记得在最后累加答案时加入 i 和 i+n 颜色不同的情况的贡献。时间复杂度 O(n)。