概要
解説がなさそうだったので書きますシリーズ。
参考資料
- アリ本 p.104 ～ p.105
- JOI 春合宿 2018 講義資料「双対性」：https://www.slideshare.net/wata_orz/ss-91375739
解法
最短路問題の双対
$p_v\leq p_u + x_{uv}$ という条件がたくさん与えられたとき、全てを満たす実数列 $(p_v)_v$ の存在判定問題を考えます。これは、次のようにして解けます。
- $u$ から $v$ に向かう重み $x_{uv}$ の有向辺を張り、有向グラフ $G$ を作る
- 解 $(p_v)_v$ の存在と、$G$ に負閉路が存在しないことは同値である
- したがって、解の存在の判定は、Bellman-Ford algorithm により判定できる
同値性について、軽く説明します。
負閉路が存在すると解が存在しないこと：解 $(p_v)_v$ があったとする。負閉路に沿った不等式 $p_v\leq p_u + x_{uv}$ の列を考えて、すべての不等式の総和を考えることで、左辺・右辺それぞれの総和をとると、矛盾が導かれる。
負閉路が存在しないと解が存在すること：まず、グラフ $G$ に適当な super node $S$ を追加して、$S$ から各頂点へ重み $0$ の有向辺を張ります。そのあと、$S$ から各 $v$ への最短路長を $p_v$ とすれば、条件を満たします。最短路長が定義されるために、負閉路が存在しないことを利用します。
注意
上述の問題において、「すべての $p_v$ に一斉に定数 $c$ を加える」という操作は、不等式の解を保ちます。したがって例えば $v_0$ を固定したとき、「解 $(p_v)_v$ の存在」と、「解 $(p_v)_v$ であって $p_{v_0} = 0$ となるものの存在」は同値です。
本問題の解法
$T$ を固定した場合の判定問題を解きます。「固定されている値」を除いて考え、固定されていない $p_v$ に対する条件に書き直すと、与えられる不等式は次の形の $3$ 種です。
- $p_u\leq p_w + x$
- $0\leq p_w + x$
- $p_u \leq 0 + x$
ここで新たに $p_0 = 0$ という記号を導入すると、これらの制約は全て $p_u\leq p_w + x$ の形で表すことができます。上の注意により、$p_0 = 0$ という制約をなくして存在判定を行ってもよく、これは Bellman-Ford algorithm による負閉路判定により解けるのでした。
グラフ構築、 Bellman–Ford algorithm による解の存在判定を二分探索の中で行うことで、最適な $T$ を求めることができます。まとめると全体として、計算量 $O(NM\log c_{\max})$ 時間で本問題を解くことができます。
