ABC061 D Score Attack - 足跡-sokuseki-

問題概要

$N$ 頂点 $M$ 辺の有向グラフが与えられ、 $i$ 番目の辺は頂点 $a_i$ から頂点 $b_i$ をコスト $c_i$ でつないでいる。
頂点1から頂点 $N$ に行くときの合計コストの最大値を求めよ。なお、合計コストをいくらでも大きくできるときはinfを出力せよ。

制約
$2 \le N \le 1000$
$1 \le M \le min(N(N-1), 2000)$
$1 \le a_i , b_i \le N$
$- 10^9 \le c_i \le 10^9$

解法

コストの正負を逆にすることでグラフの最短距離を求める問題になる。以下はコストの正負を逆にして考える。

まず、グラフの最短距離をいくらでも小さくできるときというのは、グラフに距離が負の閉路が存在するときのみなので、頂点1から頂点 $N$ の経路の途中に負の閉路があった場合はinfを出力する。
そうでない場合は、単純に頂点1から頂点 $N$ までの最短距離が答えとなる。

最短距離を求めるのと負の閉路を検出するのにはベルマンフォードを使う。

ベルマンフォードは単一始点の最短距離を求めるアルゴリズムで計算量は $O(NM)$ 。
特徴はコストが負の辺があっても正しく計算できることと、コストが負の閉路を検出できること*1。

ベルマンフォードのアルゴリズムは、始点から始点の距離を0、始点から始点以外の頂点の距離を $\infty$ として、「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」を $N-1$ 回くりかえす。

「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」という操作をしたとき、必ず1つ以上の頂点の、始点からの距離が確定することがわかる。任意の頂点間の辺の数は高々 $N-1$ 本なので、この操作を $N-1$ 回繰り返せば、すべての頂点に対する始点からの距離が求められるはずである。

しかし、これには例外があって、コストが負の閉路があった場合、最短距離はいくらでも小さくできるので、この操作を $N-1$ 回繰り返しても始点からの距離が確定せず、 $N$ 回目の操作でも始点からの距離を短くすることができる。よって、 $N$ 回目の操作で始点からの距離を更新する頂点が存在すれば、そこに負の閉路が存在することがわかる。

以上のことから今回の問題では

辺のコストの正負を逆にして、ベルマンフォードをする。
その後、頂点1から頂点 $N$ の経路に負の閉路があるかを確かめ、あればinfを、なければ頂点1から頂点 $N$ の距離を符号を逆にして答える。

をすればよい。

頂点1から頂点 $N$ の経路に負の閉路があるかを確かめる方法は、ベルマンフォードをしたあとに、さらに「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」を $N$ 回くりかえし、そのあいだに頂点 $N$ の最短距離が更新されれば、経路中に負の閉路があるということがわかる。

負の閉路がある場合、ベルマンフォード直後の「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」操作で、負の閉路に含まれる頂点のうち少なくとも1つがわかる。その後にその操作を $N-1$ 回繰り返すことで、負の閉路中にある頂点から到達できるすべての頂点について、最短距離が更新されるからである。

Submission #2125589 - AtCoder Beginner Contest 061

*1:コストが負の辺が存在しない場合は、より計算量が小さいダイクストラ( $O(ElogV)$ ) を使うべき