pub fn dinic<V, W, R, F>(
n: usize,
s: V,
t: V,
vs: impl Iterator<Item = V> + Clone,
zero: W,
index: impl Fn(&V) -> usize + Copy,
delta: impl Fn(&V) -> F + Copy,
rev: impl Fn(&V, &R) -> Rc<RefCell<W>> + Copy
) -> Wwhere
V: Clone,
W: Ord + Clone + AddAssign + SubAssign,
R: Clone,
F: Iterator<Item = (V, Rc<RefCell<W>>, R)>,Expand description
Dinic 法に基づく最大流。
Idea
todo!()
Complexity
$O(|V|^2|E|)$ 時間。
辺容量が整数のとき、多くのパラメータによって bound できることが知られている。 以下の条件は、高々定数個の例外があってもよい。
- 最大流を $F$ として $O(F|E|)$ 時間。
- 辺容量が高々 $k$ のとき $O(k\,|E|^{3/2})$ 時間。
- 辺容量が高々 $k$ で多重辺がないとき $O(k\,|V|^{2/3}|E|)$ 時間。
- 各頂点を通れるフロー量が高々 $k$ のとき $O(k\,|V|^{1/2}|E|)$ 時間。
- $k \ge \max_v \min\{\sum_{e\in\delta^+(v)} u_e, \sum_{e\in\delta^-(v)} u_e\}$.
- 二部マッチングであれば $k = 1$ であり、$O(|V|^{1/2}|E|)$ 時間。
Examples
次のようなグラフを考える。 Wikipedia にある例である。
10 4 10
+--------> [1] ----> [3] -------+
| | \ ^ 4 |
| | \ 8 | v
[0] 2 | \--> [4] ----> [5]
| | ^ 10
| 10 v 9 |
+--------> [2] -------+
流れるフローは次の通りで、$19$ である。
- $(0, 1, 3, 5)$ に $4$
- $(0, 1, 4, 5)$ に $6$
- $(0, 2, 4, 5)$ に $4$
- $(0, 2, 4, 3, 5)$ に $5$
use std::cell::RefCell;
use std::rc::Rc;
use nekolib::graph::dinic;
let es = vec![
vec![(1, 10), (2, 10)], // 0
vec![(2, 2), (3, 4), (4, 8)], // 1
vec![(4, 9)], // 2
vec![(5, 10)], // 3
vec![(3, 6), (5, 10)], // 4
vec![], // 5
];
let n = es.len();
let g = {
let mut g = vec![vec![]; 6]; // [from]: [(to, capacity, rev), ...]
for from in 0..n {
for &(to, capacity) in &es[from] {
let from_len = g[from].len();
let to_len = g[to].len();
g[from].push((to, Rc::new(RefCell::new(capacity)), to_len));
g[to].push((from, Rc::new(RefCell::new(0)), from_len));
}
}
g
};
let index = |&v: &usize| v;
let delta = |&v: &usize| g[v].iter().map(|&(nv, ref w, r)| (nv, w.clone(), r));
let rev = |&nv: &usize, &r: &usize| g[nv][r].1.clone();
let s = 0;
let t = n - 1;
let max_flow = dinic(n, s, t, 0..n, 0, index, delta, rev);
assert_eq!(max_flow, 19);