CodeChef - Short in Average

• 問題
• AC

$A$から$B$へのウォークが与えられたとする。このウォークが閉路を含んでいて閉路の平均長がウォークの平均長より小さいなら、何回も回ればウォークの平均長を閉路の平均長まで下げられるし、そうでないなら閉路を除いて損しない。また、閉路を含まないウォークは高々$N-1$本の辺しか含まない。従って、以下のようなアルゴリズムが考えられる:

1. $B$に到達できる頂点の集合$W \subseteq V$を求めて、以降は$W$による誘導部分グラフ上で考える。
   • この時点で$A$と$B$がつながっていなければ終わり。
2. Bellman-Ford法のようなDPをして、高々$N-1$辺を通るという条件の下での$A$から$B$までの最短平均長ウォークの長さを求める。
3. $A$から到達できる最短平均長閉路の長さを求める。
4. 2と3の小さいほうを取る。

実装上は3のアルゴリズムが2のDPを含んでいる。2は$N-1$回、3は$N$回回す必要があるので、最初から$N$回回せばよい。

3については、$\operatorname{dp}[k][v] =$ちょうど$k$本の辺を使う場合の$S$から$v$への最短経路、として

$$L = \min_{v \in N}\max_{k = 0, ..., N-1} \frac{\operatorname{dp}[N][v] - \operatorname{dp}[k][v]}{N-k}$$

が求める長さである。ただし、$S$から到達できない頂点がある時にそのまま扱うと$\infty - \infty$という計算が起きてしまうので、$\operatorname{dp}[N][v] = \infty$の場合は除いて計算する。全部そう（＝$N$回目で到達できる頂点がない）なら閉路がないグラフなので$L = \infty$になるべきで、つじつまがあっている。

解説は「平均長が$L$以下のウォークが存在するか？」という判定問題を解いて二分探索する方針だった。判定問題は、すべての辺の重みから$L$を引いた時に$S$から$T$への長さ$0$以下のウォークが存在するかどうかで判定できて、これはやはりBellman-Fordで調べられる。