haar_lib/matching/
bi_match.rs

1//! 二部マッチング
2
3use crate::flow::MaxFlow;
4
5/// 最大フローによる最大二部マッチング
6pub struct BipartiteMatching<F> {
7    left: usize,
8    right: usize,
9    flow: F,
10    s: usize,
11    t: usize,
12}
13
14impl<F: MaxFlow<Cap = u64>> BipartiteMatching<F> {
15    /// 左側の頂点数が`left`、右側の頂点数が`right`の空の二部グラフを用意する。
16    pub fn new(left: usize, right: usize) -> Self {
17        let mut flow = F::new(left + right + 2);
18        let s = left + right;
19        let t = s + 1;
20
21        for i in 0..left {
22            flow.add_edge(s, i, 1);
23        }
24        for i in 0..right {
25            flow.add_edge(left + i, t, 1);
26        }
27
28        Self {
29            left,
30            right,
31            flow,
32            s,
33            t,
34        }
35    }
36
37    /// 左側`i`と右側`j`に辺を張る。
38    pub fn add_edge(&mut self, i: usize, j: usize) {
39        assert!(i < self.left);
40        assert!(j < self.right);
41        self.flow.add_edge(i, self.left + j, 1);
42    }
43
44    /// 最大マッチングの辺数を返す。
45    pub fn matching(&mut self) -> u64 {
46        self.flow.max_flow(self.s, self.t)
47    }
48}
haar_lib/matching/bi_match.rs

haar_lib/matching/
bi_match.rs
