nekolib/graph/
dinic_.rs

1//! 最大流 (Dinic)。
2
3use std::cell::RefCell;
4use std::collections::VecDeque;
5use std::iter::Peekable;
6use std::ops::{AddAssign, SubAssign};
7use std::rc::Rc;
8
9/// Dinic 法に基づく最大流。
10///
11/// # Idea
12/// `todo!()`
13///
14/// # Complexity
15/// $O(|V|^2|E|)$ 時間。
16///
17/// 辺容量が整数のとき、多くのパラメータによって bound できることが知られている。
18/// 以下の条件は、高々定数個の例外があってもよい。
19///
20/// - 最大流を $F$ として $O(F|E|)$ 時間。
21/// - 辺容量が高々 $k$ のとき $O(k\\,|E|^{3/2})$ 時間。
22/// - 辺容量が高々 $k$ で多重辺がないとき $O(k\\,|V|^{2/3}|E|)$ 時間。
23/// - 各頂点を通れるフロー量が高々 $k$ のとき $O(k\\,|V|^{1/2}|E|)$ 時間。
24///     - $k \\ge \\max\_v \\min\\{\\sum\_{e\\in\\delta^+(v)} u\_e, \\sum\_{e\\in\\delta^-(v)} u\_e\\}$.
25///     - 二部マッチングであれば $k = 1$ であり、$O(|V|^{1/2}|E|)$ 時間。
26///
27/// # Examples
28///
29/// 次のようなグラフを考える。
30/// [Wikipedia](https://en.wikipedia.org/wiki/Dinic%27s_algorithm#Example) にある例である。
31///
32/// ```text
33///       10           4       10
34///  +--------> [1] ----> [3] -------+
35///  |           | \       ^ 4       |
36///  |           |  \  8   |         v
37/// [0]        2 |   \--> [4] ----> [5]
38///  |           |         ^   10
39///  |    10     v     9   |
40///  +--------> [2] -------+
41/// ```
42///
43/// 流れるフローは次の通りで、$19$ である。
44///
45/// - $(0, 1, 3, 5)$ に $4$
46/// - $(0, 1, 4, 5)$ に $6$
47/// - $(0, 2, 4, 5)$ に $4$
48/// - $(0, 2, 4, 3, 5)$ に $5$
49///
50/// ```
51/// use std::cell::RefCell;
52/// use std::rc::Rc;
53///
54/// use nekolib::graph::dinic;
55///
56/// let es = vec![
57///     vec![(1, 10), (2, 10)],       // 0
58///     vec![(2, 2), (3, 4), (4, 8)], // 1
59///     vec![(4, 9)],                 // 2
60///     vec![(5, 10)],                // 3
61///     vec![(3, 6), (5, 10)],        // 4
62///     vec![],                       // 5
63/// ];
64/// let n = es.len();
65/// let g = {
66///     let mut g = vec![vec![]; 6]; // [from]: [(to, capacity, rev), ...]
67///     for from in 0..n {
68///         for &(to, capacity) in &es[from] {
69///             let from_len = g[from].len();
70///             let to_len = g[to].len();
71///             g[from].push((to, Rc::new(RefCell::new(capacity)), to_len));
72///             g[to].push((from, Rc::new(RefCell::new(0)), from_len));
73///         }
74///     }
75///     g
76/// };
77///
78/// let index = |&v: &usize| v;
79/// let delta = |&v: &usize| g[v].iter().map(|&(nv, ref w, r)| (nv, w.clone(), r));
80/// let rev = |&nv: &usize, &r: &usize| g[nv][r].1.clone();
81///
82/// let s = 0;
83/// let t = n - 1;
84/// let max_flow = dinic(n, s, t, 0..n, 0, index, delta, rev);
85/// assert_eq!(max_flow, 19);
86/// ```
87///
88/// # References
89/// - <https://misawa.github.io/others/flow/dinic_time_complexity.html>
90pub fn dinic<V, W, R, F>(
91    n: usize,
92    s: V,
93    t: V,
94    vs: impl Iterator<Item = V> + Clone,
95    zero: W,
96    index: impl Fn(&V) -> usize + Copy,
97    delta: impl Fn(&V) -> F + Copy,
98    rev: impl Fn(&V, &R) -> Rc<RefCell<W>> + Copy,
99) -> W
100where
101    V: Clone,
102    W: Ord + Clone + AddAssign + SubAssign,
103    R: Clone,
104    F: Iterator<Item = (V, Rc<RefCell<W>>, R)>,
105{
106    let mut res = zero.clone();
107    loop {
108        let level = dual(n, s.clone(), zero.clone(), index, delta);
109        if level[index(&t)] == n {
110            break;
111        }
112        let iter: Vec<_> = vs
113            .clone()
114            .map(|v| Rc::new(RefCell::new(delta(&v).peekable())))
115            .collect();
116        loop {
117            match primal(&s, &t, zero.clone(), &level, index, rev, &iter) {
118                Some(f) => res += f,
119                None => break,
120            }
121        }
122    }
123    res
124}
125
126fn dual<V, W, R, F>(
127    n: usize,
128    s: V,
129    zero: W,
130    index: impl Fn(&V) -> usize,
131    delta: impl Fn(&V) -> F,
132) -> Vec<usize>
133where
134    V: Clone,
135    W: Ord + Clone + AddAssign + SubAssign,
136    R: Clone,
137    F: Iterator<Item = (V, Rc<RefCell<W>>, R)>,
138{
139    let mut level = vec![n; n];
140    let mut q = VecDeque::new();
141    level[index(&s)] = 0;
142    q.push_back(s);
143    while let Some(v) = q.pop_front() {
144        let i = index(&v);
145        for (nv, w, _) in delta(&v) {
146            let ni = index(&nv);
147            if *w.borrow() > zero && level[ni] == n {
148                level[ni] = level[i] + 1;
149                q.push_back(nv);
150            }
151        }
152    }
153    level
154}
155
156fn primal<V, W, R, I>(
157    s: &V,
158    t: &V,
159    zero: W,
160    level: &[usize],
161    index: impl Fn(&V) -> usize,
162    rev: impl Fn(&V, &R) -> Rc<RefCell<W>>,
163    iter: &[Rc<RefCell<Peekable<I>>>],
164) -> Option<W>
165where
166    V: Clone,
167    W: Ord + Clone + AddAssign + SubAssign,
168    R: Clone,
169    I: Iterator<Item = (V, Rc<RefCell<W>>, R)>,
170{
171    let ti = index(t);
172    let mut es = vec![];
173    let mut vis = vec![index(s)];
174    'find_path: while let Some(&vi) = vis.last() {
175        if vi == ti {
176            break;
177        }
178        loop {
179            if let Some((nv, w, r)) = iter[vi].borrow_mut().peek() {
180                let nvi = index(&nv);
181                if *w.borrow() > zero && level[vi] < level[nvi] {
182                    es.push((w.clone(), nv.clone(), r.clone()));
183                    vis.push(nvi);
184                    continue 'find_path;
185                }
186            } else {
187                break;
188            }
189
190            iter[vi].borrow_mut().next();
191        }
192        es.pop();
193        vis.pop();
194        if let Some(&vi) = vis.last() {
195            iter[vi].borrow_mut().next();
196        }
197    }
198
199    if es.is_empty() {
200        return None;
201    }
202
203    let f = es.iter().map(|(e, _, _)| e.borrow().clone()).min().unwrap();
204
205    for (w, nv, r) in es {
206        *w.borrow_mut() -= f.clone();
207        *rev(&nv, &r).borrow_mut() += f.clone();
208    }
209
210    Some(f)
211}
212
213#[test]
214fn dinic_misawa_hack() {
215    // https://gist.github.com/MiSawa/47b1d99c372daffb6891662db1a2b686
216    let n = 500;
217    let (s, a, b, c, t) = (0, 1, 2, 3, 4);
218    let mut uv = (5, 6);
219    let mut es = vec![
220        (s, a, 1),
221        (s, b, 2),
222        (b, a, 2),
223        (c, t, 2),
224        (a, uv.0, 3),
225        (a, uv.1, 3),
226    ];
227    while uv.1 + 2 < n {
228        let nuv = (uv.0 + 2, uv.1 + 2);
229        for &x in &[uv.0, uv.1] {
230            for &y in &[nuv.0, nuv.1] {
231                es.push((x, y, 3));
232            }
233        }
234        uv = nuv;
235    }
236    es.push((uv.0, c, 3));
237    es.push((uv.1, c, 3));
238
239    let g = {
240        let mut g = vec![vec![]; n];
241        for (from, to, capacity) in es {
242            let from_len = g[from].len();
243            let to_len = g[to].len();
244            g[from].push((to, Rc::new(RefCell::new(capacity)), to_len));
245            g[to].push((from, Rc::new(RefCell::new(0)), from_len));
246        }
247        g
248    };
249
250    let index = |&v: &usize| v;
251    let delta =
252        |&v: &usize| g[v].iter().map(|&(nv, ref w, r)| (nv, w.clone(), r));
253    let rev = |&nv: &usize, &r: &usize| g[nv][r].1.clone();
254    let flow = dinic(n, s, t, 0..n, 0, index, delta, rev);
255
256    assert_eq!(flow, 2);
257}
nekolib/graph/dinic_.rs

nekolib/graph/
dinic_.rs
