competitive/graph/
maximum_flow.rs

1use super::{BidirectionalSparseGraph, Bounded, Graph, Zero};
2use std::ops::{Add, AddAssign, Sub, SubAssign};
3
4#[derive(Debug, Clone)]
5pub struct DinicBuilder<C> {
6    vsize: usize,
7    edges: Vec<(usize, usize)>,
8    capacities: Vec<C>,
9}
10impl<C> DinicBuilder<C> {
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: C)
19    where
20        C: Zero + PartialOrd,
21    {
22        self.edges.push((from, to));
23        assert!(cap >= C::zero());
24        self.capacities.push(cap);
25        self.capacities.push(C::zero());
26    }
27    pub fn gen_graph(&mut self) -> BidirectionalSparseGraph {
28        let edges = std::mem::take(&mut self.edges);
29        BidirectionalSparseGraph::from_edges(self.vsize, edges)
30    }
31    pub fn build(self, graph: &BidirectionalSparseGraph) -> Dinic<'_, C> {
32        let DinicBuilder {
33            vsize, capacities, ..
34        } = self;
35        Dinic {
36            graph,
37            capacities,
38            iter: Vec::with_capacity(vsize),
39            level: Vec::with_capacity(vsize),
40            deq: Vec::with_capacity(vsize),
41        }
42    }
43}
44impl<C> Extend<(usize, usize, C)> for DinicBuilder<C>
45where
46    C: Zero + PartialOrd,
47{
48    fn extend<I: IntoIterator<Item = (usize, usize, C)>>(&mut self, iter: I) {
49        for (from, to, cap) in iter {
50            self.add_edge(from, to, cap)
51        }
52    }
53}
54
55#[derive(Debug, Clone)]
56pub struct Dinic<'a, C> {
57    graph: &'a BidirectionalSparseGraph,
58    capacities: Vec<C>,
59    iter: Vec<usize>,
60    level: Vec<usize>,
61    deq: Vec<usize>,
62}
63impl<'a, C> Dinic<'a, C>
64where
65    C: Copy + Zero + Ord + Bounded + Add<Output = C> + Sub<Output = C> + AddAssign + SubAssign,
66{
67    pub fn builder(vsize: usize, esize_expect: usize) -> DinicBuilder<C> {
68        DinicBuilder::new(vsize, esize_expect)
69    }
70    fn bfs(&mut self, s: usize, t: usize) -> bool {
71        self.level.clear();
72        self.level.resize(self.graph.vertices_size(), usize::MAX);
73        self.level[s] = 0;
74        self.deq.clear();
75        self.deq.push(s);
76        let mut head = 0;
77        while head < self.deq.len() {
78            let u = self.deq[head];
79            head += 1;
80            for a in self.graph.neighbors(u) {
81                if self.capacities[a.label] > 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(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.neighbors(u).skip(self.iter[u]) {
98            if self.level[u] > self.level[a.to] && self.capacities[a.label ^ 1] > C::zero() {
99                let d = self.dfs(s, a.to, (upper - res).min(self.capacities[a.label ^ 1]));
100                if d > C::zero() {
101                    self.capacities[a.label ^ 1] -= d;
102                    self.capacities[a.label] += 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(s);
139        let mut head = 0;
140        while head < self.deq.len() {
141            let u = self.deq[head];
142            head += 1;
143            for a in self.graph.neighbors(u) {
144                if self.capacities[a.label] > C::zero() && !visited[a.to] {
145                    visited[a.to] = true;
146                    self.deq.push(a.to);
147                }
148            }
149        }
150        visited
151    }
152    pub fn get_flow(&self, eid: usize) -> C {
153        self.capacities[eid * 2 + 1]
154    }
155    pub fn change_edge(&mut self, eid: usize, cap: C, flow: C) {
156        assert!(flow <= cap);
157        self.capacities[eid * 2] = cap - flow;
158        self.capacities[eid * 2 + 1] = flow;
159    }
160}
competitive/graph/maximum_flow.rs

competitive/graph/
maximum_flow.rs
