PKU 3169 Layout

蟻本復習中。

問題

N頭の牛が、順に一直線に並ぶ。
牛には好き嫌いがあり、ML個の好きの関係およびMD個の嫌いの関係がある。

好きの関係は3つの整数AL,BL,DLにより指定され、
ALの牛とBLの牛が距離DL以内にいなければならないことを表す。

嫌いの関係は3つの整数AD,BD,DDにより指定され、
ADの牛とBDの牛が距離DD以上離れなければならないことを表す。

このとき、1番目の牛とN番目の牛の距離の最大値を求めよ。
いくらでも離れられるときは-2を、並び順が存在しないときは-1を出力せよ。
なお、複数頭の牛が同じ位置に立つこともできる。

制約条件

N≦1000
ML,MD≦10000
DL,DD≦10^9

方針

蟻本p104の解説の通り。

• 牛が順に並んでいるという制約はd[i]≦d[i+1]と表され、
• 好きの関係はBL≦AL+DL
• 嫌いの関係はBD≧AD+DD

という不等式で書ける。

これは線形計画問題になっているが、
不等式に現れる変数が各辺1つ（かつ符号が一緒）なので、
グラフの最短経路問題に帰着できる。

グラフの始点sからの、頂点iの最短距離をd[i]と置く。
重みwの辺u→vがあったとき、不等式
d[v]≦d[u]+wが成り立つ。
逆に、この不等式を全て満たすようなdはd[i]-d[s]の最大値がsからiへの最短距離になっている。

ちょっと直感的にイメージが沸かないので類題を解きたいのだけど、どこかにないだろうか……