準備：牛ゲーについて

次の形の最適化問題を考えます。

\[\begin{aligned} \max_{x_1, \dots, x_N} \quad & x_T - x_S \\ \textrm{s.t.} \quad & x_{V_j} - x_{U_j} \leq W_j \: (1 \leq j \leq M) \end{aligned}\]

この問題の解は、\(N\) 頂点 \(M\) 辺からなり、\(j\) 番目の辺が \(U_j \to V_j\) に向かう重み \(W_j\) の有向辺であるようなグラフ \(G\) を考えると、（\(G\) に負閉路が存在せず、\(S\textrm{-}T\) パスが存在するとき）\(G\) の \(S\textrm{-}T\) 最短路長に一致することが知られています。この典型は俗に「牛ゲー」と呼ばれています。

牛ゲーの中身についての解説は蟻本やインターネット上の記事などを参考にするとよいと思います。（概要：線形計画問題である。双対問題を考える。有向グラフの接続行列が完全ユニモジュラであることから整数計画問題としてよく、最短路問題のような問題（ただし閉路の扱いが異なる）と解釈できる。）

本問題の解法

最終的な上の歯の長さ \(u_i\)、上の歯と下の歯の長さの和 \(h\) を変数とすると、\(h\) を最大化する問題と考えることができ、制約条件は

• 上の歯の長さ \(0 \leq u_i \leq U_i\)
• 下の歯の長さ \(0 \leq h - u_i \leq D_i\)
• \(|u_i - u_{i+1}| \leq X\)

と書くことができます。ここで \(h = c_T - c_S, c_i = c_T - u_i\) とおくと、最大化するものは \(c_T - c_S\) で、それぞれの制約条件は

• \(0 \leq c_T - c_i \leq U_i\)
• \(0 \leq c_i - c_S \leq D_i\)
• \(-X \leq c_{i+1} - c_i \leq X\)

と整理されるので、牛ゲーの形に帰着できました（注：たとえば \(0 \leq c_T - c_i \leq U_i\) は \(c_T - c_i \leq U_i\) かつ \(c_i - c_T \leq 0\) と考えればよいです）。

変数のおきかたによっては辺重みが負の最短路問題に帰着されてしまうことがあるので注意してください。