library_checker/graph/
min_cost_b_flow.rs1use competitive::graph::NetworkSimplex;
2use competitive::prelude::*;
3
4#[verify::library_checker("min_cost_b_flow")]
5pub fn min_cost_b_flow(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, m, b: [i64; iter n]);
8 let mut ns = NetworkSimplex::<i64, i128>::new(n);
9 for (i, b) in b.enumerate() {
10 ns.add_demand_supply(i, b);
11 }
12 sc!(edges: [(usize, usize, i64, i64, i128); iter m]);
13 for (s, t, l, u, c) in edges {
14 ns.add_edge(s, t, l, u, c);
15 }
16 let sol = ns.solve_minimize();
17 if let Some(sol) = sol {
18 pp!(@lf sol.cost, @it sol.potentials, @it sol.flows);
19 } else {
20 pp!("infeasible");
21 }
22}