既存投稿一覧ページへのリンク
最大フロー問題
雑記
競技プログミングをやればやるほど、競技プログラミングの鉄則は完璧にしておいた方が良いという思いが強くなり、再読。
最大フロー問題に対しては、苦手意識がこびりついているので、脳内トレースをしまくっておくことにしました。
入力サンプル01
下記の入力サンプルでトレース
7 11
1 6 6
1 4 5
1 2 6
5 6 9
4 3 23
2 5 5
3 5 16
4 5 18
4 6 9
6 7 10
5 7 12
Step01. 順フローの最小値の経路を通過し、通過した経路に逆辺(残余グラフ)を張る
Step02. 順フローの最小値の経路を通過し、通過した経路に逆辺(残余グラフ)を張る(2回目)
Step03. 順フローの最小値の経路を通過し、通過した経路に逆辺(残余グラフ)を張る(3回目)
このとき、流せる経路がなくなるため、最大流量は「16」という解になる。
補足
Step02.で「5->4->6->7」という逆辺(残余グラフ)を使う経路を使ったとしても、Step03.で「6->4->5->7」の経路を使うことになるから結局は行って来いになるため、最終的には同じ答えになるってことですね。
入力サンプル02
下記の入力サンプルでトレース
7 11
1 6 16
1 4 6
1 2 22
5 6 23
4 3 24
2 5 18
3 5 8
4 5 11
4 6 15
6 7 19
5 7 24
Step01. 順フローの経路を通過し、通過した経路に逆辺(残余グラフ)を張る
Step02. 順フローの経路を通過し、通過した経路に逆辺(残余グラフ)を張る(2回目)
Step03. 順フローの経路を通過し、通過した経路に逆辺(残余グラフ)を張る(3回目)
※ Step02.で残余グラフを作成したので、逆向きにフローを流せる
Ans.
最終雨滴に流せる流量は「40」となる
雑記
トレースしながら思い出したけど、小学校くらいの頃、こういうパズルゲームみたいなやつやっていて、頭の良い子はサラッと「5->6->7」に分岐する経路を見つけ出してたけど、この経路は直感じゃ見つけづらいですよね。
こういう経路に対して、手順を使って凡人にも導き出せるようになるからこそ、アルゴリズムの学習は重要ですね。
アルゴリズムのイメージはできてるけど、コーディングするには逆辺(残余グラフ)を張るところに苦戦するので、今しばらくは脳内トレースを繰り返すことにします。
まぁ、100題くらいやれば、忘れなくなると思いますので。。。