cp_library_rs/graph/
ford_fulkerson.rs

1//! Ford-Fulkerson法
2
3use num_traits::PrimInt;
4use rustc_hash::FxHashMap;
5
6#[derive(Debug, Clone)]
7pub struct Edge<T> {
8    /// 逆向きの辺の番号
9    rev: usize,
10    from: usize,
11    to: usize,
12    cap: T,
13    original_cap: T,
14}
15
16impl<T: Clone> Edge<T> {
17    pub fn new(rev: usize, from: usize, to: usize, cap: T) -> Self {
18        Self {
19            rev,
20            from,
21            to,
22            cap: cap.clone(),
23            original_cap: cap,
24        }
25    }
26}
27
28type Graph<T> = Vec<Vec<Edge<T>>>;
29
30/// FordFulkerson法を実行する
31#[derive(Debug)]
32pub struct FordFulkerson<T> {
33    N: usize,
34    /// 残余ネットワーク
35    pub G: Graph<T>,
36    /// 辺の番号
37    edge_id: FxHashMap<(usize, usize), usize>,
38}
39
40impl<T: PrimInt> FordFulkerson<T> {
41    pub fn new(n: usize) -> Self {
42        Self {
43            N: n,
44            G: vec![vec![]; n],
45            edge_id: FxHashMap::default(),
46        }
47    }
48
49    /// 有向辺を追加する
50    pub fn add_edge(&mut self, from: usize, to: usize, cap: T) {
51        let rev = self.G[to].len();
52        self.G[from].push(Edge::new(rev, from, to, cap));
53        // 逆向き辺を追加
54        let rrev = self.G[from].len() - 1;
55        self.G[to].push(Edge::new(rrev, to, from, T::zero()));
56        // 辺のidを追加
57        self.edge_id.insert((from, to), rrev);
58    }
59
60    /// uからtへのフロー追加路を見つける
61    fn dfs(u: usize, t: usize, f: T, G: &mut Graph<T>, visit: &mut [bool]) -> T {
62        if u == t {
63            return f;
64        }
65        visit[u] = true;
66        for i in 0..G[u].len() {
67            let v = G[u][i].to;
68            let cap = G[u][i].cap;
69            if visit[v] || cap <= T::zero() {
70                continue;
71            }
72            let d = Self::dfs(v, t, f.min(cap), G, visit);
73            if d > T::zero() {
74                // 前向き辺の更新
75                G[u][i].cap = cap - d;
76                // 後ろ向き辺の更新
77                let r = G[u][i].rev;
78                G[v][r].cap = G[v][r].cap + d;
79
80                return d;
81            }
82        }
83        T::zero()
84    }
85
86    /// 最大流を求める
87    pub fn max_flow(&mut self, s: usize, t: usize) -> T {
88        let mut flow = T::zero();
89        let mut visit = vec![false; self.N];
90        loop {
91            visit.fill(false);
92            // フロー追加路を見つける
93            let f = Self::dfs(s, t, T::max_value(), &mut self.G, &mut visit);
94            if f.is_zero() {
95                break;
96            }
97            flow = flow + f;
98        }
99        flow
100    }
101
102    /// 現在の状態での辺(u,v)の流量を求める
103    pub fn get_flow(&self, u: usize, v: usize) -> T {
104        let i = self.edge_id[&(u, v)];
105        let cap = self.G[u][i].cap;
106        let original = self.G[u][i].original_cap;
107        original - cap
108    }
109}
cp_library_rs/graph/ford_fulkerson.rs

cp_library_rs/graph/
ford_fulkerson.rs
