Dinic法について - TAISA_'s blog理解にかなり手間取った&面白かったのでメモ。 アルゴリズム やっていることは、「長さが短い順に増加路を使っていく」というだけ。 以下、頂点数 、辺数 、始点 、終点 のネットワークを考える。 残余グラフを構築しておく。 増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。 BFSで、「容量正の辺のみを使った時の、 から までの最短路長」 を求める。 長さ の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 なる辺 以外はないものとして扱えば、増加路は全て長さ になる。 DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 に辿り着けなかった時と、容量が0になった時、辺は死ぬ。 なお、辺が死んでも1回のステップが終わったら復活する。 計算量(一般のグラフの場
