「CF1253F」Cheap Robot
给出一个包含 n 个点 m 条边的简单无向连通带权图。节点编号为 1 \sim n,其中恰好有 k 个充电中心,编号为 1 \sim k。
有一个电池容量为 c 的机器人在图中移动,任意时刻电量 x 必须为区间 [0, c] 中的整数。经过一条长度为 w 的边需要消耗 w 的电量,每当到达一个充电中心时,其电池将会充满。
有 Q 次询问,每次询问给出 a, b,你需要求出机器人从 a 到 b 至少需要的电池容量 c 是多少。
数据范围:2 \leq k \leq n \leq 10^5,1 \leq m, Q \leq 3 \times 10^5,1 \leq w \leq 10^9,1 \leq a, b \leq k,a \neq b。
时空限制:3s / 512MiB。
Solution
若所有节点均为充电桩,则从 a 走到 b 的答案,即为 a, b 之间所有简单路径上最大边权的最小值。此时只需求出最小生成树,使用树上倍增求出 a, b 之间的最大边权即可。
记 \mathrm{dist}_u 表示距离 u 最近的充电桩的距离,可以用多源点 dijkstra 求出。
但正常情况下可能要经过非充电桩的节点。考虑一个贪心策略:每次走到一个节点的时候,都去距离它最近的一个充电桩补满电量再回来。
由于起点与终点均为充电桩,若要经过原图上的一条边 (x, y, z),电池容量至少为 \mathrm{dist}_x + z + \mathrm{dist}_y(至少要从充电桩走到其中一个端点,经过这条边,再从另外一个端点走到充电桩)。
故对于每条边 (x, y, z),使用 \mathrm{dist}_x + z + \mathrm{dist}_y 代替它的边权。此时从 a 走到 b 的答案,即为 a, b 之间所有简单路径上最大边权的最小值。