competitive/graph/
maximum_flow.rs

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

competitive/graph/
maximum_flow.rs
