library_checker/graph/
bipartitematching.rs

1#[doc(no_inline)]
2pub use competitive::graph::{BipartiteMatching, DinicBuilder};
3use competitive::prelude::*;
4
5#[verify::library_checker("bipartitematching")]
6pub fn bipartitematching_dinic(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, l, r, m, ab: [(usize, usize); m]);
10    let mut builder = DinicBuilder::new(l + r + 2, m + l + r);
11    let s = l + r;
12    let t = s + 1;
13    for (a, b) in ab.iter().cloned() {
14        builder.add_edge(a, b + l, 1);
15    }
16    for a in 0..l {
17        builder.add_edge(s, a, 1);
18    }
19    for b in 0..r {
20        builder.add_edge(b + l, t, 1);
21    }
22    let graph = builder.gen_graph();
23    let mut dinic = builder.build(&graph);
24    let f = dinic.maximum_flow(s, t);
25    writeln!(writer, "{}", f).ok();
26    for (i, (a, b)) in ab.iter().enumerate() {
27        if dinic.get_flow(i) > 0 {
28            writeln!(writer, "{} {}", a, b).ok();
29        }
30    }
31}
32
33#[verify::library_checker("bipartitematching")]
34pub fn bipartitematching(reader: impl Read, mut writer: impl Write) {
35    let s = read_all_unchecked(reader);
36    let mut scanner = Scanner::new(&s);
37    scan!(scanner, l, r, m, ab: [(usize, usize); m]);
38    let mut bm = BipartiteMatching::from_edges(l, r, &ab);
39    let matching = bm.maximum_matching();
40    writeln!(writer, "{}", matching.len()).ok();
41    for (x, y) in matching {
42        writeln!(writer, "{} {}", x, y).ok();
43    }
44}
library_checker/graph/bipartitematching.rs

library_checker/graph/
bipartitematching.rs
