AOJ2304: Reverse Roads

グラフ

問題↓

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2304

問題概要

  • 有向グラフが与えられます。
  • 与えられた有向グラフの辺をいくつでも逆向きにすることができます。
  • sからtの最大流を最大化して下さい。
  • また、その時に向きを変えた辺を出力して下さい。
  • スペシャルジャッジ

解法

  • 両方向に辺を貼って最大流を求める。
  • Ford-Fullkerson法で最大流を求めた時、使った辺のキャパシティは減らされる。（この場合は0になる)
  • 最初 (x -> y c=1)  (x->y c=0) というあるノードから同じ別のノードに対して二組の有向辺とその逆辺がある。（cはキャパシティ)
  • x->yの辺を使ったということは、(x->y c=0)  (y->x c=1) になっているはずなので、x->yが最初に与えられた辺の逆であるものを列挙する。
ソースコード

感想

usedの初期化を忘れてたり、redfsで打ち切るタイミング間違えてたりで焦った。

最大流の理解が深まる良い問題。