Function nekolib::graph::dinic

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)>,

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);

References

• https://misawa.github.io/others/flow/dinic_time_complexity.html