haar_lib/flow/
ford_fulkerson.rs

1//! 最大流 (Ford-Fulkerson)
2
3pub use crate::flow::*;
4
5#[derive(Clone, Debug)]
6struct Edge {
7    to: usize,
8    rev: usize,
9    cap: u64,
10    is_rev: bool,
11}
12
13/// Ford-Fulkerson法
14#[derive(Clone)]
15pub struct FordFulkerson {
16    size: usize,
17    edges: Vec<Vec<Edge>>,
18}
19
20impl FordFulkerson {
21    fn dfs(&mut self, cur: usize, sink: usize, flow: u64, check: &mut [bool]) -> u64 {
22        if cur == sink {
23            flow
24        } else {
25            check[cur] = true;
26            let n = self.edges[cur].len();
27
28            for i in 0..n {
29                let e = self.edges[cur][i].clone();
30                if !check[e.to] && e.cap > 0 {
31                    let d = self.dfs(e.to, sink, std::cmp::min(flow, e.cap), check);
32                    if d > 0 {
33                        self.edges[cur][i].cap -= d;
34                        self.edges[e.to][e.rev].cap += d;
35                        return d;
36                    }
37                }
38            }
39            0
40        }
41    }
42}
43
44impl MaxFlow for FordFulkerson {
45    type Cap = u64;
46
47    fn new(size: usize) -> Self {
48        Self {
49            size,
50            edges: vec![vec![]; size],
51        }
52    }
53
54    fn add_edge(&mut self, u: usize, v: usize, cap: Self::Cap) {
55        let rev = self.edges[v].len();
56        self.edges[u].push(Edge {
57            to: v,
58            rev,
59            cap,
60            is_rev: false,
61        });
62        let rev = self.edges[u].len() - 1;
63        self.edges[v].push(Edge {
64            to: u,
65            rev,
66            cap: 0,
67            is_rev: true,
68        });
69    }
70
71    fn max_flow(&mut self, s: usize, t: usize) -> Self::Cap {
72        let mut ret = 0;
73
74        loop {
75            let mut check = vec![false; self.size];
76            let flow = self.dfs(s, t, u64::MAX, &mut check);
77            if flow == 0 {
78                return ret;
79            }
80            ret += flow;
81        }
82    }
83
84    fn get_edges(&self, i: usize) -> Vec<(usize, u64)> {
85        self.edges[i]
86            .iter()
87            .filter(|e| !e.is_rev)
88            .map(|e| (e.to, e.cap))
89            .collect()
90    }
91
92    fn reset(&mut self) {
93        todo!();
94    }
95}
haar_lib/flow/ford_fulkerson.rs

haar_lib/flow/
ford_fulkerson.rs
