【每日一题】5月1日题目精讲 最小生成树

题号 NC20568
名称 [SCOI2012]滑雪与时间胶囊
来源 [SCOI2012]
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

第一问是个裸的搜索不多说。
因为题目说不考虑时间胶囊的消耗，而且可以连续食用，所以最后走出来的形状一定是树的样子。
但是它并不是简单的最小生成树，因为他的边实际上是有方向的，即只能从高层走到低层（同层之间的双向边可以做两个单向边处理）。下图给出一组不考虑方向直接跑最小生成树的反例：

这种有向图的"最小生成树"实际上是最小树形图问题，最小树形图问题也有它自己的“朱-刘Edmonds算法”有兴趣的同学可以自己去研究（是的，这里不讲），他的复杂度是的，对于本题来说是不够的。
如果我们非常想用最小生成树去做他（因为确实问题很相似，想尽办法用自己会的算法去解决它是非常正常也是很正确的选择），那么我们需要详细分析最小生成树算法，以及本题的特殊性 。
首先考虑最小生成树的原理——贪心的选一条边加进来，直到加入了n-1条边（prim算法是每次找链接现有生成树和零散点的最短的一条边，而kruskal是找最短的把两个集合合并的边，但不管怎么说都是贪心找边）。
那么本题，如果我们想选一条边a到b，这条边需要满足什么条件呢？
显然，高度更高的点a要已经和根节点连通了（即之前选的边已经能从根走到a），那么我们有个很简单的方法来解决这个问题——在kruskal算法的排序中按照出点的高度从大到小排序（第一关键字），高度相同再按照长度排序，这样相当于我们在一层一层扩展，先把最高层的点加入最小树形图然后次高层然后第三高层……这样所有的边就是按照从高的低的方向走的了。（prim算法是不是也这样请大家自行考虑，多想想没坏处）

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月8日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴