library_checker/graph/
assignment.rs

1#[doc(no_inline)]
2pub use competitive::graph::NetworkSimplex;
3use competitive::prelude::*;
4
5#[verify::library_checker("assignment")]
6pub fn assignment(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [[i64; n]; n]);
10    let mut ns = NetworkSimplex::<i64, i64>::new(n * 2);
11    for (i, a) in a.iter().enumerate() {
12        ns.add_supply(i, 1);
13        ns.add_demand(i + n, 1);
14        for (j, &a) in a.iter().enumerate() {
15            ns.add_edge(i, j + n, 0, 1, a);
16        }
17    }
18    let sol = ns.solve_minimize();
19    if let Some(sol) = sol {
20        iter_print!(writer, sol.cost);
21        let p = (0..n * n)
22            .filter(|&eid| sol.flows[eid] != 0)
23            .map(|eid| eid % n);
24        iter_print!(writer, @it p);
25    } else {
26        iter_print!(writer, "infeasible");
27    }
28}