[BZOJ4736/UOJ274]温暖会指引我们前行(LCT)

发布于 2018-01-25  13 次阅读


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

本文链接地址:[BZOJ4736/UOJ274]温暖会指引我们前行(LCT)

Description

虽然小R住的宿舍楼早已来了暖气,但是由于某些原因,宿舍楼中的某些窗户仍然开着(例如厕所的窗户),这就使得宿舍楼中有一些路上的温度还是很低。

小R的宿舍楼中有nn个地点和一些路,一条路连接了两个地点,小R可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始,小R还不熟悉宿舍楼中的任何一条路,所以他会慢慢地发现这些路,他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。
小R需要在宿舍楼中活动,每次他都需要从一个地点到达另一个地点。小R希望每次活动时经过一条最温暖的路径,最温暖的路径的定义为,将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高,在满足该条件的情况下,温度第二低的路温度尽量高,以此类推。小R不会经过重复的路。由于每条路的温度互不相同,因此只存在一条最温暖的路径。
对于小R的每次活动,你需要求出小R需要走过的路径总长度。如果小R通过当前发现的路不能完成这次活动,则输出 −1−1。
注意本题中的字典序与传统意义上的字典序定义有所不同,对于两个序列a,b(a≠b)a,b(a≠b),若aa是bb的前缀则aa的字典序较大,同时可以推出空串的字典序最大。

Http

BZOJ
UOJ

Tag

LCT

解决思路

题目中说的什么字典序最大。说白了就是要求温度的最大生成树,直接用\(LCT\)维护即可。

代码

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

本文链接地址:[BZOJ4736/UOJ274]温暖会指引我们前行(LCT)


HNCJ OIer 一枚