让世界遗忘歌

题解

/ 注册

全部文章 / 题解（共1篇）

题解 | #新春游戏之数学系列#

H 如果我们把所有的点两两之间连边，题目很明显是找到该图的一个最小生成树。现在我们需要减少边的数量。首先容易想到当两个点之间的距离为 ,但两个点之间已经有一条简单路径长度为，且满足,则这条长度为的边是没有必要的。考虑把所有点按排序，并在相邻的两点之间连边。接着对进行同样的操作。可以证明没...

最小生成树贪心

2024-02-04

2 114