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

最小流量制限付き最大流

SRMで最小流量制限付き最大流が出ました。(SRM694Div1 Hard)
どうやるのが正統派なやり方なのか、わかる方がいれば教えてほしいのですが、とりあえず自分がやった方法をメモしておきます。

まず、下図のようなグラフのs→tの最大流が求めたいとする。
f:id:snuke:20160710041224j:plain
以下のように変換する。(蟻本に載ってる図と同様)
f:id:snuke:20160710041307j:plain
超頂点S,Tを作り、u→vにL以上R以下の辺があるとき「u→vにR-L(黒)」「u→TにL(青)」「S→vにL(青)」の辺を張る。
「S→sに∞(緑)」「t→Tに∞(赤)」の辺も張る。
この変換により、最小流量制限を外す準備は整った。
しかし、このまま流すと青の辺に十分な量が流れない可能性がある。
そこで、以下の手順でフローを流す。
1. 緑と赤の容量を0にして流す
2. 緑の容量を∞、赤の容量を0にして流す
3. 緑の容量を0、赤の容量を∞にして流す
4. 緑と赤の容量を∞にして流す
このように流すことによって、青の辺を優先的に使うフローが求まる。
こう流したあとの残余グラフで青の辺に容量が残っていたら条件を満たすフローが存在しない。
(追記:コメントで教えてもらったのですが、緑と赤を張らずに、S→T・s→T・S→t・s→tの順に流せばもっと楽ですね。)

また、上記と同じようなことが最小費用流でも実現できる。
緑と赤の辺だけのコストを1にして残りを0にすればいい。
実行速度は遅くなるが、実装は楽そうだ。


フローまだまだ知らないことがあるなぁ・・・とりあえず、最小費用循環流の解き方が知りたい。