けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2872 最短距離を伸ばすえびちゃん (RUPC 2018 day3-F)

ABC 051 D - Candidates of No Shortest Paths をやった流れで。この問題なら自然だけど、ちょっと設定変えた問題に超グロ問があったりする (AOJ 2230 How to Create a Good Game)。

問題へのリンク

問題概要

 N 頂点  M 辺の重み付き有向グラフが与えられる。グラフの各辺の重みを適切に増やすことで、2 頂点 s, t 間の最短路長を増やしたい。各辺  e の重みを 1 増やすのに必要なコストが  c_e で与えられる。

s-t 間の最短路長を 1 以上増やすのに必要な最小コストを求めよ。

制約

  •  2 \le N \le 200
  •  1 \le M \le 2000

考えたこと

s-t 間の最短路として採用されるはずもない辺については、伸ばしても意味がなさそう。また、特定の辺について 2 以上重みを増やす意味はなさそう。ということで、「重みを 1 だけ増やす辺集合のうち、それらの  c_e の値の総和の最小値」を求める問題だと言える。

とりあえず、s-t 間の最短路に使われることがありうる辺をすべて列挙してみる。

このうちの 1 本の距離を 1 伸ばしたところで、他に迂回路が取れてしまうかもしれない。よって、s-t 間の最短路に使われうる辺のみを取り出して他は除去してできるグラフにおいて、

  • s-t カットを 1 つ選んで、それらの辺の重みを 1 ずつ増やしたもの

がとりあえず自明な上界になる。逆に s-t 間の最短路長を増やせるならば、1 増やす辺の集合が s-t 間を分断していなければならない。

というわけで、s-t 間の最小カットを求めれば良いことがわかる。