MCMF

The APIs of this snippet is similar to those of Dinic's.

The algorithm used for finding shortest path for MCMF is SPFA.

Code

mod mcmf {
    //! Reference: https://github.com/justiceHui/SSU-SCCC-Study/blob/master/2022-winter-adv/slide/04.pdf

    use std::collections::VecDeque;

    #[derive(Clone)]
    pub struct Edge {
        pub dst: u32,
        pub opp: u32,
        pub cap: u64,
        pub cost: i64,
    }

    impl Edge {
        fn new(dst: usize, opp: usize, flow: u64, cost: i64) -> Self {
            Self {
                dst: dst as u32,
                opp: opp as u32,
                cap: flow,
                cost,
            }
        }
    }

    pub struct Mcmf {
        pub n: usize,
        pub g: Vec<Vec<Edge>>,
    }

    impl Mcmf {
        pub fn new(n: usize) -> Self {
            Self {
                n,
                g: vec![vec![]; n],
            }
        }

        pub fn add_edge(&mut self, s: usize, e: usize, c: u64, d: i64) {
            let (slen, elen) = (self.g[s].len(), self.g[e].len());
            self.g[s].push(Edge::new(e, elen, c, d));
            self.g[e].push(Edge::new(s, slen, 0, -d));
        }

        fn augment(
            &mut self,
            s: usize,
            t: usize,
            prv: &mut [usize],
            idx: &mut [usize],
            dst: &mut [i64],
        ) -> bool {
            let mut inn = vec![false; self.n];
            dst.fill(i64::MAX);
            let mut queue = VecDeque::new();
            inn[s] = true;
            dst[s] = 0;
            queue.push_back(s);

            while let Some(v) = queue.pop_front() {
                inn[v] = false;
                for (i, e) in self.g[v].iter().enumerate() {
                    let src = e.dst as usize;
                    if e.cap != 0 && dst[src] > dst[v] + e.cost {
                        dst[src] = dst[v] + e.cost;
                        prv[src] = v;
                        idx[src] = i;
                        if !inn[src] {
                            inn[src] = true;
                            queue.push_back(src);
                        }
                    }
                }
            }
            dst[t] < i64::MAX
        }

        pub fn min_cost_max_flow(&mut self, s: usize, t: usize) -> (u64, i64) {
            use std::iter::successors;
            let mut flow = 0;
            let mut cost = 0;

            let mut prv = vec![0; self.n];
            let mut idx = vec![0; self.n];
            let mut dst = vec![0; self.n];
            while self.augment(s, t, &mut prv, &mut idx, &mut dst) {
                let path = successors(Some(t), |&i| Some(prv[i]))
                    .take_while(|&i| i != s)
                    .map(|i| self.g[prv[i]][idx[i]].cap)
                    .min()
                    .unwrap();
                flow += path;
                cost += path as i64 * dst[t];
                for i in successors(Some(t), |&i| Some(prv[i])).take_while(|&i| i != s) {
                    self.g[prv[i]][idx[i]].cap -= path;
                    let j = self.g[prv[i]][idx[i]].opp as usize;
                    self.g[i][j].cap += path;
                }
            }

            (flow, cost)
        }
    }
}