haar_lib/flow/
dinic.rs

1//! 最大流 (Dinic)
2//!
3//! # References
4//! - <https://misawa.github.io/others/flow/dinic_time_complexity.html>
5
6pub use crate::flow::*;
7use std::collections::VecDeque;
8
9#[derive(Clone, Debug)]
10struct Edge {
11    to: usize,
12    rev: usize,
13    cap: u64,
14    is_rev: bool,
15}
16
17/// Dinic法
18#[derive(Clone)]
19pub struct Dinic {
20    _size: usize,
21    edges: Vec<Vec<Edge>>,
22    first_edge: Vec<usize>,
23    level: Vec<usize>,
24}
25
26impl Dinic {
27    fn dfs(&mut self, cur: usize, sink: usize, mut min_cap: u64) -> u64 {
28        if cur == sink {
29            min_cap
30        } else {
31            let mut f = 0;
32
33            for i in self.first_edge[cur]..self.edges[cur].len() {
34                let e = self.edges[cur][i].clone();
35                if e.cap > 0 && self.level[e.to] > self.level[cur] {
36                    let df = self.dfs(e.to, sink, min_cap.min(e.cap));
37
38                    min_cap -= df;
39
40                    let e = &mut self.edges[cur][i];
41                    e.cap -= df;
42
43                    let Edge { to, rev, .. } = *e;
44                    self.edges[to][rev].cap += df;
45
46                    f += df;
47
48                    let e = &self.edges[cur][i];
49                    if df > 0 && e.cap > 0 {
50                        self.first_edge[cur] = i;
51                        return f;
52                    }
53                }
54            }
55
56            self.first_edge[cur] = self.edges[cur].len();
57
58            f
59        }
60    }
61}
62
63impl MaxFlow for Dinic {
64    type Cap = u64;
65    fn new(size: usize) -> Self {
66        Self {
67            _size: size,
68            edges: vec![vec![]; size],
69            first_edge: vec![0; size],
70            level: vec![0; size],
71        }
72    }
73
74    fn add_edge(&mut self, u: usize, v: usize, cap: Self::Cap) {
75        let rev = self.edges[v].len();
76        self.edges[u].push(Edge {
77            to: v,
78            rev,
79            cap,
80            is_rev: false,
81        });
82        let rev = self.edges[u].len() - 1;
83        self.edges[v].push(Edge {
84            to: u,
85            rev,
86            cap: 0,
87            is_rev: true,
88        });
89    }
90
91    fn max_flow(&mut self, s: usize, t: usize) -> Self::Cap {
92        let mut f = 0;
93
94        loop {
95            self.level.fill(0);
96            self.level[s] = 1;
97            let mut q = VecDeque::new();
98            q.push_back(s);
99
100            while let Some(cur) = q.pop_front() {
101                for e in &self.edges[cur] {
102                    if self.level[e.to] == 0 && e.cap > 0 {
103                        self.level[e.to] = self.level[cur] + 1;
104                        q.push_back(e.to);
105                    }
106                }
107            }
108
109            if self.level[t] == 0 {
110                break f;
111            }
112
113            self.first_edge.fill(0);
114            f += self.dfs(s, t, u64::MAX);
115        }
116    }
117
118    fn get_edges(&self, i: usize) -> Vec<(usize, u64)> {
119        self.edges[i]
120            .iter()
121            .filter(|e| !e.is_rev)
122            .map(|e| (e.to, e.cap))
123            .collect()
124    }
125
126    fn reset(&mut self) {
127        todo!();
128    }
129}
haar_lib/flow/dinic.rs

haar_lib/flow/
dinic.rs
