\(T\) を固定して、\((a_v)\) の存在を判定する問題を考えると、これは「最短路問題の双対」という有名問題になります。

参考資料

• アリ本 p.104 ～ p.105
• 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\) を構成します。まず、グラフ \(G\) に適当な super node \(S\) を追加して、\(S\) から各頂点へ重み \(0\) の辺を張ります。そのあと、\(S\) から \(v\) への最短路長を \(p_v\) とすれば、条件を満たします。

本問題の解法

\(T\) を固定した判定問題を解きます。 「固定されている値」を除いて考え、固定されていない値 \(p_v\) に対する条件に書き直すと、与えられる不等式は次の 形の 3 種です。

• \(p_u \leq p_w + x\)
• \(0 \leq p_w + x\)
• \(p_u \leq x\)

\(p_0 = 0\) とした場合、これらの制約は全て \(p_u\leq p_w + x\) の形で表すことができます。

\(p_u\leq p_w + x\) の形の差分制約の解は、すべての \(p_v\) に定数を加算することで、\(p_0 = 0\) という条件を追加しても存在性は保たれます。よって、\(p_0 = 0\) とした場合の制約を追加することは妥当です。

以上のグラフ構築、 Bellman–Ford algorithm による解の存在判定を二分探索の中で行うことで、最適な \(T\) を求めることができます。