nagisa_菜鸡

题解

/ 注册

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

[SCOI2012]滑雪与时间胶囊结题报告（最小生成树）

看到这道题，发现不会最小生成树，遂昨晚熬夜补了prim算法，今天来写这道题。看到时间胶囊能回溯，因此确实可以想得到是最小生成树，其实就是最小生成树后求路径长度和最小的问题。这道唯一特别一点的地方就是只能从高处到低处，并且要保证能去的地方最多，所以贪心策略需要加一条：以边终点高的优先选择，保证高度高（...

最小生成树每日一题图论贪心

2020-05-04

0 656