PKU3169: Layout

グラフ

アリ本より、牛さんの問題。

問題文↓

http://poj.org/problem?id=3169

（日本語訳：アリ本104P)

問題概要

  • 1~N番のN匹の牛が番号順に一列に並んでいます。
  • ML個の情報AL,BL,DLが与えられ、牛ALと牛BLは距離DL以内でなければなりません。
  • MD個の情報AD,BD,DDが与えられ、牛ADと牛BDは距離DD以上でなければなりません。
  • この時の１番の牛からN番の牛の最大距離を求めなさい。
  • また、並び方が存在しない場合は-1,無限に距離を伸ばせる場合は-2を出力して下さい。

解法

  • あるグラフにおいて、a->bにコストcのエッジが伸びてるとき
    頂点aまでの最短経路をd(a)としてd(a) + c >= d(b) が成り立つ。
  • 上記の定義をもとに、d(BL) - d(AL) <= DL （ALとBL の距離の差は必ずDL以内である。）という情報と
    d(BD) - d(AD) >= DD (ADとBDの距離の差は必ずDD以上である。）という情報をグラフに起こす。
  • すると、式変形して
    d(AL) + DL >= d(BL)  -----> AL->BL にコストDLのエッジ
    d(BD) - DD >= d(AD) -----> BD->AD にコスト-DDのエッジを張ることになる。
  • また問題文よりd(a)<=d(a+1)<=d(a+2)....なので
    d(a) + 0 <= d(a+1)
    d(a+1) - 0 >= d(a) ------> すべてのaに対し a+1->a にコスト0のエッジを張ることになる。
  • 以上よりできたグラフの最短経路を求める。（負のエッジがあるのでベルマンフォード）
  • 負の経路があった場合、矛盾があるので -1
    d(N)がINFの場合、-2
    それ以外はd(N)を普通に出力
ソースコード

感想

この手の問題をこんな感じにグラフに起こして解けるってのが分かるのは良かった。

グラフの最短経路に関して　d(a) + c >= d(b) が成り立つことは自明だけど頭にしっかり入ってると発想の起因になるから覚えておいて損はないはず。