[2021年8月30日追記．ここから]
AtCoder Beginner Contest 216 G - 01Sequence の公式解説を読んだら，牛ゲーで解けると書いてあります (解いているときは思いつきもしませんでした)．そこでこの記事を昔書いたことを思い出して読み直してみました．
多分，大きくは間違ってはいないだろうと思いますが，あまり役に立つ記事ではなさそうです．大事なところは Fact2 で終わっていて，後はそれほど興味なさそうなところの処理を延々と書いていますので．
以下が元記事 (2019年5月18日投稿)．
[2021年8月30日追記．ここまで]
蟻本 の2.5節の応用問題のところに Layout (POJ No.3169) がある．そこに，特殊な線形計画問題は，グラフの最短路問題として解くことができる，と書かれている．ネット上では「牛ゲー」と呼ばれているらしい．少し検索してみたのだけれど，どうしてそれで良いのか，という説明があまり見つからなかった．(いや，きっとあるだろうとは思うけれど，十分探せていない．) まあ，そんなことは明らかだ，ということなのかもしれないが，トップから到達可能でない部分も制約を満たすようにできて，値をいくらでも大きくできる，というところがすぐにはわからなかったので，書いておく．もっとマシな考え方があったら教えてください．線形計画問題について何も知らないので，変なことを書いているかもしれない．
制約 $x_j - x_i \leq c_{ij} $ ($ (i,j) \in E $) のもとで，与えられた p, q に対して $x_q - x_p$ の最大値を求めたい．Eに現れる数をノード集合Vとして，各$(i,j) \in E$ について，$i$から$j$に距離 $c_{ij}$ のエッジがある有向グラフ G を考える．このとき，以下が成り立つことを示す．
- 制約を満たす解が存在することと，G に負閉路がないことは同値．
- Gに負閉路が無い時，制約を満たす $x_q - x_p$ がいくらでも大きくできることと，$q$ が $p$ から到達不可能なことは同値．
- Gに負閉路が無く，$q$ が $p$ から到達可能な時，$x_q - x_p$ の最大値は，$p$ から $q$ への最短路長に等しい．
まず簡単なことをチェックする．
Fact 1 Gに負閉路があると，制約を満たす解は無い．
理由: 閉路 $ i_0 \to i_1 \to \cdots i_k \to i_0 $ の距離合計が $ c < 0 $ だとする．解として
$(a_i \mid i \in V) $があるとすると，$ a_{i_{j+1}} - a_{i_j} \leq c_{,i_j ,i_{j+1}} $ ($j = 0, \ldots, k$) が成り立つので，これらを全部加えると，$ 0 \leq c $ となり，矛盾する．
Fact 2 $(a_i \mid i \in V) $ が制約を満たすとする．G において，$i$ から $j$ へのパス $i = i_0 \to i_1 \to \cdots \to i_k = j$ があるとき，このパスの長さを $l = c_{i_0 i_1} + \cdots + c_{i_{k-1} i_k}$ とすると，$a_j - a_i \leq l$ である．
理由: $a_{i_{m+1}} - a_{i_m} \leq c_{i_m i_{m+1}}$ ($m = 0, \ldots, k-1$) を全部加えれば良い．
次に，$n \not\in V$ なる $n$ をとる．Gに，ノード $n$ を追加し，各 $i \in V$ に対して $n から i$ へのエッジを追加する．エッジ$n \to p$ の長さは0, $i \neq p$ なる $i$ に対しては，エッジ $n \to i$ の長さは $M$ とする．ただし，$M$ は十分大きく，具体的には $M > |E|\times {\rm max}\{ |c_{ij}| \mid (i,j) \in E\}$ となるようにとる．このようにして作成したグラフをG'とする．各 $i \in V$ に対し，$a_i$ を，$n$ から $i$ までの最短路の長さとして定義する．
Fact 3 Gに負閉路が無い場合，$i$ が $G$ において $p$ から到達可能であれば，$ a_i $ は，$G'$ における $p$ から $i$ の最短路の長さに等しい．
理由: これがなりたつように$n$を端点とするエッジの長さを定めた．
Fact 4 Gに負閉路が無い場合，$(a_i \mid i \in V)$ は制約を満たす．
理由: $(i,j) \in E$ とする．$a_j - a_i > c_{ij}$ と仮定すると，$n$ から $i$ への最短路に $i \to j$ を加えたパスの長さは $ c_{ij} + a_i < a_j $ となってしまい，$a_j$の定義に反する．
準備ができたので，(1)-(3)を示す．
(1) Fact 1 と Fact 4 から明らか．
(2) の左から右は，Fact 2．右から左: $q$が$p$から到達できないとすると，$a_q - a_p = M - 0 = M$．Mは前述の条件の下でいくらでも大きく取れる．
(3) Fact 2から，$x_q - x_p$ は，最短路長を超えられない．一方で，Fact 4より $(a_i \mid i \in V)$ は制約を満たし，$a_q - a_p$ は，Fact 3 より，最短路長である．
(終)