2/5 PKU

3621 Sightseeing Cows

ある街にはいくつかのランドマークがあり、ランドマーク同士を結ぶ道がいくつかある。道は一方通行で、それぞれ通過するのにかかる時間が決まっている。ランドマークごとに、それを見た時の「うれしさ」が決まっている。今、牛があるランドマークから始めて、いくつかのランドマークを移動し、最初のランドマークに戻ってくるという旅行を計画している。少なくとも1つ以上のランドマークを訪れないといけない。「1分あたりのうれしさの平均値」を最大化せよ。

うれしさの平均値をある値D以上にできるかの判定を行うことを考える。
平均値は、(通ったランドマークのうれしさの合計) / (通った道の移動時間) で表されるから、(通った道の移動時間) * D - (通ったランドマークのうれしさの合計) <= 0ならよいことになる。ところで、同じランドマークを2回以上訪れてもうれしさは増えないが、2回訪れたら訪れた分だけうれしさが増えると仮定する。
すると、辺ごとに「移動時間*D - 移動先のランドマークのうれしさ」を割り当て、負閉路が存在するか判定すると判定が行えることになる。
一方このアルゴリズムにおいて、同じランドマークを2回以上訪れることに(うれしさが増えるとしても)意味はない。ある経路がa->b->c->b->aと表現できるとき(起点を除いて2回以上訪れないときには、このような表現の仕方は存在しない)、a->b, b->aの重みの和をA、b->c, c->bの重みの和をBとすると、A+B<=0よりA<=0またはB<=0であるから、a->b->aまたはb->c->bと単純化して十分であるからである。
この問題では同じランドマークを2回以上訪れてもうれしさは増えないため、このアルゴリズムが正当に動作することが示される。