[BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)

发布于 2018-02-21  8 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)

Description

a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1<=i<=N)和一高度Hi。a180285能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边,且i 的高度不小于j。 与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是a180285 滑行的距离)。请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间之前到过的景点(比如上上个经过的景点和上上上个经过的景点)。 现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗?

Http

BZOJ
Luogu

Tag

生成树

题目大意

给定一个有特殊性质的有向图,求最小树形图。

解决思路

直接把求最小树形图的朱刘算法拿过来是不行的,时间复杂度太高。
注意到这一道题中有向图的特殊性质,边总是从高的向低的走的,可以想象是按高度从高到低分成若干段来考虑。这个对于贪心很有帮助。
首先考虑为什么无向图的最小生成树算法不能直接照搬到有向图中。以\(Prim\)为例,无向图的生成树算法基于贪心原理,即若选当前距离最短的点进来不会差。但这个贪心在有向图中是不成立的,因为边有向。
放到这个题,由于边总是从高的连向低的,那么先考虑高的点不会更差,因为海拔更低的点不会更新高的点,所以我们可以类似从高到低地来考虑。又因为海拔相同的点,边相当于是无向的。所以就可以直接用无向图的最小生成树来解。
这里选择用\(Prim\)算法实现最小生成树,那么与常规的算法不一样的是,这里的比较就要优先比较海拔,再比较距离,这样才能满足上面的贪心。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)


HNCJ OIer 一枚