蟻本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
この問題も同じテクニックで解けるらしい。