読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2594 Reverse a Road Ⅱ

AOJ

この問題好き

問題文

Reverse a Road II | Aizu Online Judge

久々に訳書きます
有向辺グラフとスタート,ゴールが与えられる.
スタートからゴールまで,道が一つも被らないルートが最大でいくつあるか求めたい(頂点は被ってもよい)
ただし,一つの辺だけ向きを逆にすることができる.
実現できるルート数の最大値と,そのルート数を実現できる逆にする辺の選び方が何通りあるかをそれぞれ答えよ.
ただし逆向きにしてもルートが増えない場合は元のグラフでの最大値と0を出力すること.

解法

まあどう見ても最大流系の解法で解く問題なんですが,
とりあえず変更無しのグラフにフローをめいっぱい流してみます.

向きを変更するのではなく,新たに流量1の辺をどこかに追加することを考えると,グラフ全体の流量は最大でも1しか増えないことが分かります.
つまり,既に流れている辺の向きを逆にすることは全く意味がないことがこのことから分かります.(1減らして1増えるだけなので)

ではあとは流れていない辺を逆向きにしてチェックするだけです.
なのですが,いちいち入れ替えて流れるか試していると間に合いません.

流量が増える条件について考えてみると,残余グラフ上でスタートからゴールまでの流量1以上のパスがあればよいです.
フローをめいっぱい流した状態だと増加パスが存在しないので,

  • スタートから流量1以上の辺をたどっていける頂点(A)
  • ゴールまで流量1以上の辺をたどっていける頂点(B)
  • どっちにもたどり着けない頂点

の3種類に分かれます.

ある辺について

  • (A)->(B)である
  • まだフローが流れていない

であれば向きを逆にすることでグラフ全体の流量を増加させることができます.


というわけで残余グラフ上でスタートとゴールからBFSをして各辺を調べてやればACできます.