1 条题解
-
0
题目分析
首先能看出这是一道最短路题目。由于最终所有流浪猫都要聚集到点 ,我们用 Dijkstra 求出每个点到点 的最短路径。注意题目要求时间相同时选择编号字典序较小的路径,因此需要额外按编号顺序处理,保证得到的是一棵满足字典序要求的最短路径树。
接下来考虑如何计算总时间。先假设不增加捷径:由于所有流浪猫走向点 的路径最终会形成一棵树,也就是最短路径树,我们可以直接建出这棵树,在树上求解总时间。
求解总时间有两种方法:一是对于每个点,求出它到点 的距离再对 加权求和;二是考虑最短路径树上的每一条边,求出经过这条边的流浪猫总数,也就是该边对应子树内的猫的数量。此处第二种方式更利于后续分析。
现在考虑如何增加捷径。沿用上面的第二种方式:当子树 内的所有流浪猫都汇聚在点 时,如果在 与 之间建一条通行时间为 的捷径,那么每只猫可以少走 的时间,其中 表示点 到点 的最短距离。于是枚举所有点 ,求出节省时间的最大值即可。
需要注意题目中的细节:流浪猫只有在常规路径上"偶然发现"捷径、且捷径确实更快时才会改走捷径,因此节省量只在 时为正,否则该点无法带来收益。
- 1
信息
- ID
- 47
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者