自动搬运

查看原文

来自洛谷，原作者为

	Querainy Now fuck off Hang out with ur bitches

搬运于2025-08-24 21:49:13，当前版本为作者最后更新于2022-11-11 08:34:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像没人写题解啊。看起来就是要求关键点的最小斯坦呐树，那么考虑经典的，dfs 序会经过树上每条边两次，所以考虑从每个关键点出发跑 dijkstra，得到关键点两两之间的最短路，然后直接用它跑一个 prim。

正确性，注意到对于一个最优解，沿着它的一个 dfs 序走，就会得到若干条关键点之间的路径，它们串起来得到一条经过每个关键点至少一次的路径，而这些路径的长度和不超过最优解的两倍。显然每条路径不短于我们求出的最短路，于是我们用这些最短路求出的 mst 不比沿着这个 dfs 序走得到的链长，于是它不可能超过最优解的两倍。

实现就是两个板子。