competitive/graph/
maximum_flow.rs

1use super::BidirectionalSparseGraph;
2use std::collections::VecDeque;
3
4#[derive(Debug, Clone)]
5pub struct DinicBuilder {
6    vsize: usize,
7    edges: Vec<(usize, usize)>,
8    capacities: Vec<u64>,
9}
10impl DinicBuilder {
11    pub fn new(vsize: usize, esize_expect: usize) -> Self {
12        Self {
13            vsize,
14            edges: Vec::with_capacity(esize_expect),
15            capacities: Vec::with_capacity(esize_expect * 2),
16        }
17    }
18    pub fn add_edge(&mut self, from: usize, to: usize, cap: u64) {
19        self.edges.push((from, to));
20        self.capacities.push(cap);
21        self.capacities.push(0);
22    }
23    pub fn gen_graph(&mut self) -> BidirectionalSparseGraph {
24        let edges = std::mem::take(&mut self.edges);
25        BidirectionalSparseGraph::from_edges(self.vsize, edges)
26    }
27    pub fn build(self, graph: &BidirectionalSparseGraph) -> Dinic<'_> {
28        let DinicBuilder {
29            vsize, capacities, ..
30        } = self;
31        Dinic {
32            graph,
33            capacities,
34            iter: Vec::with_capacity(vsize),
35            level: Vec::with_capacity(vsize),
36            deq: VecDeque::with_capacity(vsize),
37        }
38    }
39}
40impl Extend<(usize, usize, u64)> for DinicBuilder {
41    fn extend<T: IntoIterator<Item = (usize, usize, u64)>>(&mut self, iter: T) {
42        for (from, to, cap) in iter {
43            self.add_edge(from, to, cap)
44        }
45    }
46}
47
48#[derive(Debug, Clone)]
49pub struct Dinic<'a> {
50    graph: &'a BidirectionalSparseGraph,
51    capacities: Vec<u64>,
52    iter: Vec<usize>,
53    level: Vec<usize>,
54    deq: VecDeque<usize>,
55}
56impl Dinic<'_> {
57    pub fn builder(vsize: usize, esize_expect: usize) -> DinicBuilder {
58        DinicBuilder::new(vsize, esize_expect)
59    }
60    fn bfs(&mut self, s: usize, t: usize) -> bool {
61        self.level.clear();
62        self.level.resize(self.graph.vertices_size(), usize::MAX);
63        self.level[s] = 0;
64        self.deq.clear();
65        self.deq.push_back(s);
66        while let Some(u) = self.deq.pop_front() {
67            for a in self.graph.adjacencies(u) {
68                if self.capacities[a.id] > 0 && self.level[a.to] == usize::MAX {
69                    self.level[a.to] = self.level[u] + 1;
70                    if a.to == t {
71                        return false;
72                    }
73                    self.deq.push_back(a.to);
74                }
75            }
76        }
77        self.level[t] == usize::MAX
78    }
79    fn dfs(&mut self, s: usize, u: usize, upper: u64) -> u64 {
80        if u == s {
81            return upper;
82        }
83        let mut res = 0;
84        for a in self.graph.adjacencies(u).skip(self.iter[u]) {
85            if self.level[u] > self.level[a.to] && self.capacities[a.id ^ 1] > 0 {
86                let d = self.dfs(s, a.to, (upper - res).min(self.capacities[a.id ^ 1]));
87                if d > 0 {
88                    self.capacities[a.id ^ 1] -= d;
89                    self.capacities[a.id] += d;
90                    res += d;
91                    if upper == res {
92                        break;
93                    }
94                }
95            }
96            self.iter[u] += 1;
97        }
98        res
99    }
100    pub fn maximum_flow_limited(&mut self, s: usize, t: usize, limit: u64) -> u64 {
101        let mut flow = 0;
102        while flow < limit {
103            if self.bfs(s, t) {
104                break;
105            }
106            self.iter.clear();
107            self.iter.resize(self.graph.vertices_size(), 0);
108            while flow < limit {
109                let f = self.dfs(s, t, limit - flow);
110                if f == 0 {
111                    break;
112                }
113                flow += f;
114            }
115        }
116        flow
117    }
118    pub fn maximum_flow(&mut self, s: usize, t: usize) -> u64 {
119        self.maximum_flow_limited(s, t, u64::MAX)
120    }
121    pub fn minimum_cut(&mut self, s: usize) -> Vec<bool> {
122        let mut visited = vec![false; self.graph.vertices_size()];
123        visited[s] = true;
124        self.deq.clear();
125        self.deq.push_back(s);
126        while let Some(u) = self.deq.pop_front() {
127            for a in self.graph.adjacencies(u) {
128                if self.capacities[a.id] > 0 && !visited[a.to] {
129                    visited[a.to] = true;
130                    self.deq.push_back(a.to);
131                }
132            }
133        }
134        visited
135    }
136    pub fn get_flow(&self, eid: usize) -> u64 {
137        self.capacities[eid * 2 + 1]
138    }
139    pub fn change_edge(&mut self, eid: usize, cap: u64, flow: u64) {
140        assert!(flow <= cap);
141        self.capacities[eid * 2] = cap - flow;
142        self.capacities[eid * 2 + 1] = flow;
143    }
144}
competitive/graph/maximum_flow.rs

competitive/graph/
maximum_flow.rs
