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

ゆらのふなびと

競プロ, Python, C++

【メモ】Ford-Fulkerson法、Dinic法について

フローのアルゴリズム2種類を勉強したので、メモです。

ろくに問題を解かず蟻本を写経しただけの段階で書いているので、記述が無辺世界にふっとんでいる可能性があります。

Ford-Fulkerson法

残余ネットワーク上の増加路をDFSで検出し、そこに流せるだけ流す。これを収束するまで繰り返す。

最悪$F$回DFSをする(毎回1しか流量が増えない場合)ので、計算量は$O(F|E|)$。

Dinic法

最短の増加路を検出し、そこに流せるだけ流す。これを収束するまで繰り返す。

最短の増加路長は、フローを流すごとに単調非減少。そこで以下の1, 2を繰り返す。

  1. BFSをして最短路長$L$を求める
  2. 長さ$L$のパスをDFSで検出し、そこに流せるだけ流す。これを長さ$L$のパスがなくなるまで繰り返す。

2が収束したとき、最短路長はstrictlyに増加している。よってBFSは$O(|V|)$回、おのおの$O(|E|)$で行われる。

蟻本実装のiter配列は、無駄な辺を何度も調べないようにするためのアイデア。(パスを辞書順に見ているイメージ?)これにより2のDFSが1つの$L$について$O(|E||V|)$でできるので、全体の計算量は$O(|V|(|E| + |E||V|)) = O(|E||V|^2)$となる。実際にはもっと早く動くらしい。