[做题记录-图论] [NEERC2017]Journey from Petersburg to Moscow [关于处理路径前$k$大的一种方法]

题意

给定一张连通无向简单图 \(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\)的时候答案正确。

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

上一篇:POJ 2488 - A Knight‘s Journey + Python


下一篇:Dynamitic Programming journey