最大流(Dinic)
説明
最大流を求める。最短の増加パスを探して、そこにフローを流していくことを繰り返す。そのような経路がなくなったら残余パスでもう一度それを繰り返す。それでも、流せなくなったら終了する。実際の計算量よりも高速に動作することが知られている。
最大流は最小カットと一致する。
計算量
$O(E V^2)$
実装例
応用: 燃やす埋める
以下の制約問題は最小カットで解くことが出来る。
- すべての頂点に $\{0, 1\}$ を割り当てる。
- 頂点 $x_i$ が $0$ で頂点 $y_i$ が $1$ に割り当てられたとき $z_i$ 失う。
- 失う重みの和の最小値を求めよ。
必ず $0$ に割り当てられる頂点 $S$, $1$ に割り当てられる頂点 $T$ がある。それぞれの制約 $(x_i, y_i, z_i)$ に対し, 「頂点 $x_i$ から頂点 $y_i$ に容量 $z_i$ の辺を張った」あと, 頂点 $S$ から頂点 $T$ への最小カットを求めると, 失う重みの和の最小値となっている。
以下のように色々な制約を $(x_i, y_i, z_i)$ の形に変形することができる。
- $x$ が $0$ のとき $z$ 失う → $x$ が $0$ で $T$ が $1$ のとき $z$ 失う → $(x, T, z)$
- $x$ が $1$ のとき $z$ 失う → $S$ が $0$ で $x$ が $1$ のとき $z$ 失う → $(S, x, z)$
- $x$ が $0$ のとき $z$ 得る → 無条件で $z$ 得る + $x$ が $1$ のとき $z$ 失う
- $x$ が $1$ のとき $z$ 得る → 無条件で $z$ 得る + $x$ が $0$ のとき $z$ 失う
- $x$ が $0$ で $y$ が $0$ のとき $z$ 得る → 無条件で $z$ 得る + 新たな頂点 $w$ を考え, $w$ が $1$ のとき $z$ 失う + $w$ が $0$ で $x, y$ が $1$ のとき $\infty$ 失う($w$ が $1$ のときは $z$ 失う代わりに $x, y$ は自由になるが, $w$ が $0$ のときは $x, y$ を必ず $0$ にしたい)
- $x$ が $1$ で $y$ が $1$ のとき $z$ 得る → 無条件で $z$ 得る + 新たな頂点 $w$ を考え, $w$ が $0$ のとき $z$ 失う + $x, y$ が $0$ で $w$ が $1$ のとき $\infty$ 失う
但し以下の制約があるときは最大カットになるため NP-完全(らしい)。
- $x$ が $0$ で $y$ が $0$ のとき $z$ 失う
- $x$ が $0$ で $y$ が $1$ のとき $z$ 得る