library_checker/graph/
bipartitematching.rs

1use competitive::graph::{BipartiteMatching, DinicBuilder};
2use competitive::prelude::*;
3
4#[verify::library_checker("bipartitematching")]
5pub fn bipartitematching_dinic(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(l, r, m, ab: [(usize, usize); m]);
8    let mut builder = DinicBuilder::new(l + r + 2, m + l + r);
9    let s = l + r;
10    let t = s + 1;
11    for (a, b) in ab.iter().cloned() {
12        builder.add_edge(a, b + l, 1);
13    }
14    for a in 0..l {
15        builder.add_edge(s, a, 1);
16    }
17    for b in 0..r {
18        builder.add_edge(b + l, t, 1);
19    }
20    let graph = builder.gen_graph();
21    let mut dinic = builder.build(&graph);
22    let f = dinic.maximum_flow(s, t);
23    let ans = ab
24        .into_iter()
25        .enumerate()
26        .filter_map(|(i, edge)| (dinic.get_flow(i) > 0).then_some(edge));
27    pp!(f; @ittup ans);
28}
29
30#[verify::library_checker("bipartitematching")]
31pub fn bipartitematching(reader: impl Read, writer: impl Write) {
32    prepare_io!(reader, writer);
33    sc!(l, r, m, ab: [(usize, usize); m]);
34    let mut bm = BipartiteMatching::from_edges(l, r, &ab);
35    let matching = bm.maximum_matching();
36    pp!(matching.len(); @ittup matching);
37}
library_checker/graph/bipartitematching.rs

library_checker/graph/
bipartitematching.rs
