最小流量制限付き最大流 - 少ない学びをせめて記録する

勉強した。

難しいしよく理解できてない気がするので考えたことのメモ。

上の記事のS→Tのフロー、s→Tのフロー、S→tのフローをできるだけ流した後のことを考えるとイメージがついた。
この状態で超頂点S,Tを作る逆の処理をするとどのような状態か考えてみる。S,Tを作るとき、u→vの辺を、u→v、S→v、u→Tの3つに分解した。後ろ2つの辺は今ともに最小流量b流れている。（流れていない場合は条件を満たすフローは存在しない）なのでu→vのフローにb加えてS→v、u→Tは消せばいい。こうして最小流量制限付きのグラフに戻すと、全ての辺において最小流量を満たすフローが流れている。各vの流入量=流出量も当然満たしているし、そのために最初流量+α流れている辺もある。

最後のS→s、t→Tに無限辺を張ってフローを流す操作では追加で流せるだけ流して最終的な値を計算している。Sに入る辺はないので、このタイミングで満たした必須辺からフローが減るようなことはない。
こうして得られた値は辺を分解したときに最小流量bを2つに分けたので2回分計算されている。本来の最大流と合わせるために全辺のbの和を引かないといけない。

わからなかったこと。

必須辺に全て流れることを確認した後なら（S→Tへの最大流 - 全ての辺の最小流量制限の和）がs→tの本来の最大流になるらしい（蟻本より）。このとき必須辺を満たさないけど、上手くやって本来より大きなフローを流すようなことは何故起こらないのか。
他にもあった気がしたけど忘れた。