Open Wflight opened 5 years ago
https://wflight.github.io/2019/06/23/%E6%BB%91%E9%9B%AA-%E9%A2%98%E8%A7%A3/
查看原题请戳这里 解题思路首先，因为题目要求求“即满足经过景点数最大的前提下使得滑行总距离最小”，所以这道题目我们可以用最小生成树来解决。 具体做法核心算法 这里推荐用kruskal去求最小生成树(prim虽然加上堆优化也应该不会超时，但是ta真的是代码难敲效率还低qwq)。 因为这道题目对于每个点的高度都有一个限制，所以有些点即使是有边相连也是到不了的。此时我们可以先统计可以到达的边，然后只
test
Wflight
commented
5 years ago Wflight
commented
5 years ago
https://wflight.github.io/2019/06/23/%E6%BB%91%E9%9B%AA-%E9%A2%98%E8%A7%A3/
查看原题请戳这里 解题思路首先，因为题目要求求“即满足经过景点数最大的前提下使得滑行总距离最小”，所以这道题目我们可以用最小生成树来解决。 具体做法核心算法 这里推荐用kruskal去求最小生成树(prim虽然加上堆优化也应该不会超时，但是ta真的是代码难敲效率还低qwq)。 因为这道题目对于每个点的高度都有一个限制，所以有些点即使是有边相连也是到不了的。此时我们可以先统计可以到达的边，然后只