Skip to main content

aizu_online_judge/grl/
grl_7_a.rs

1use competitive::graph::DinicBuilder;
2use competitive::prelude::*;
3
4#[verify::aizu_online_judge("GRL_7_A")]
5pub fn grl_7_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(xs, ys, es, edges: [(usize, usize); iter es]);
8    let mut builder = DinicBuilder::new(xs + ys + 2, xs + ys + es);
9    let s = xs + ys;
10    let t = s + 1;
11    for x in 0..xs {
12        builder.add_edge(s, x, 1);
13    }
14    for y in 0..ys {
15        builder.add_edge(y + xs, t, 1);
16    }
17    for (x, y) in edges {
18        builder.add_edge(x, y + xs, 1);
19    }
20    let graph = builder.gen_graph();
21    let mut dinic = builder.build(&graph);
22    pp!(dinic.maximum_flow(s, t));
23}