library_checker/graph/
min_cost_b_flow.rs

1#[doc(no_inline)]
2pub use competitive::graph::NetworkSimplex;
3use competitive::prelude::*;
4
5#[verify::library_checker("min_cost_b_flow")]
6pub fn min_cost_b_flow(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, m, b: [i64; n], edges: [(usize, usize, i64, i64, i128); m]);
10    let mut ns = NetworkSimplex::<i64, i128>::new(n);
11    for (i, b) in b.into_iter().enumerate() {
12        ns.add_demand_supply(i, b);
13    }
14    for (s, t, l, u, c) in edges {
15        ns.add_edge(s, t, l, u, c);
16    }
17    let sol = ns.solve_minimize();
18    if let Some(sol) = sol {
19        iter_print!(writer, sol.cost);
20        for i in 0..n {
21            iter_print!(writer, sol.potentials[i]);
22        }
23        for i in 0..m {
24            iter_print!(writer, sol.flows[i]);
25        }
26    } else {
27        iter_print!(writer, "infeasible");
28    }
29}