wrp 划水记录 (cnblogs.com)

题意

给定一张连通无向简单图 $G$,每条边有一个边权。
给定正整数 $k$,你需要找到 $G$ 的一条从 $1$ 到 $n$ 的路径,设该路径的长度为 $l$,你需要使得这条路径中边权前 $\min\left{ k, l \right}$ 大的边的边权总和尽可能小。

题解

这种玩意看着人傻了, 一点想法没有, 瞟了下 yhx 的题意下面几行发现好像是减什么东西才有想法

考虑枚举一条边作为第 $k$大, 那么如果把所有的边减去这个 $w_k$并对 $0$取 $\max$, 然后如果把权补回来, 那么就求出了一条合法的路径。

考虑直接大力枚举每条边和初始不变的情况计算, 那么 $Ans = \min_{w_k}{Dis_{n} + k \times w_k}$。

下面考虑证明这个事情。

令 $l$表示答案的路径长度。

  • 若 $l \geq k$。
    • 如果路径上有 $> k$条变化后有权值的边,那么当前答案会 $\geq ans$。因为多出来的边应该不算。
    • 如果路径上有 $\leq k$条变化后有权值的边,那么当前答案会 $\geq ans$。因为多加了。
    • 当当前枚举的 $w$恰好是答案路径的 $w_k$时, 当前答案就是 $ans$, 所以正确。
  • 若 $l < k$
    • 当 $w = 0$的时候答案正确。

综上可以发现在没有取到答案的时候我们的做法会使答案变大, 恰好取到的时候会是答案, 直接最短路即可。

分类: 文章

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注