aizu_online_judge/grl/
grl_7_a.rs

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