蟻本P.104 の Layout (POJ No.3169) の解説を読んで学んだ。

単一始点最短経路問題を連立不等式で表す

単一始点最短経路問題を考える。

AからDへの最短経路を求める。

cost[X] で node A からのnode X までの最短距離を表す。求めたいのは、cost[D]。

cost[A] = 0
# edge A - B
cost[B] <= cost[A] + 10 
cost[A] <= cost[B] + 10
# edge A - C
cost[A] <= cost[C] + 30
cost[C] <= cost[A] + 30
# edge A - D
cost[A] <= cost[D] + 50
cost[D] <= cost[A] + 50
# edge B - D
cost[B] <= cost[D] + 20
cost[D] <= cost[B] + 20
# edge C - D
cost[C] <= cost[D] + 40
cost[D] <= cost[C] + 40

# ----> cost[D] を求める。

これは、ダイクストラ法やベルマンフォード法を用いて求めることができる。
(エッジのコストが負になりうる場合は、ベルマンフォード一択。)

Layout (POJ No.3169) (牛ゲー) に適応する

これは以下の連立不等式を解けば良い。

# `cows[i]` で牛iの座標を表す。

cows[1] = 0

# 牛は番号順に並んでいる。(1 <= x <= n - 1)
cows[x] <= cows[x+1] 

# 仲の悪い牛 x と y は min_dist 以上離れる必要がある。(x < y)
cows[x] + min_dist <= cows[y]
# <=> x <-- -min_dist -- y

# 仲の良い牛 x と y は max_dist 以下の距離にいる必要がある。(x < y)
cows[y] <= cows[x] + max_dist
# <=> x --- max_dist --> y

# ----> cows[N] - cows[1] = cows[N] の最大値を求める。

問題で与えられた例でいうと、

牛は４匹
1 と 3 の max_dist = 10
2 と 4 の max_dist = 20
2 と 3 の min_dist = 3

cows[0] = 0
cows[1] <= cows[2]
# <=> 1 <---0---- 2
cows[2] <= cows[3]
# <=> 2 <---0---- 3
cows[3] <= cows[4]
# <=> 3 <---0---- 4

cows[2] <= cows[1] + 10
# <=> 1 ---10---> 2
cows[4] <= cows[2] + 20
# <=> 2 ---20---> 4
cows[2] + 3 <= cows[3]
# <=> 2 <--(-3)-- 3

# ------------> cows[4] の最大値を求めよ。

これを以下のように、うまくグラフに落とし込む。

これで、node 1 -> 4 の最短経路を求めれば良い。
TODO: なぜ最短経路が cows[4]の最大値になるのかわからない。

なお、これは older->younger のエッジのコストが0以下であるため、可能になっている？？？

younger <--(0-)--- older

この問題では、エッジのコストが負になりうるため、ベルマンフォードを使う。なお、

N回目の更新でも、テーブル内で最短コストの更新が行われる <=> 条件を満たす並び方が存在しない
最短経路が求まらない <=> cows[4] は cows[1] から無限大の距離離れることができる

らしい。
TODO: 理解する。

Ref

この問題も同じテクニックで解けるらしい。