CS MCMF

struct Edge {
    to: int,
    next: int,
    cap: int,
    cost: int
}

struct Queue {
	l: int[],
    r: int[],
    function push(self: Queue, x: int) { self.l.push(x); }
    function pop(self: Queue) -> int {
        if (self.r.length() > 0) {
            let x = self.r[self.r.length() - 1];
            self.r.pop();
            return x;
        }
        while (self.l.length() > 0) {
            let x = self.l[self.l.length() - 1];
            self.l.pop();
            self.r.push(x);
        }
        let x = self.r[self.r.length() - 1];
        self.r.pop();
        return x;
    }
    function empty(self: Queue) -> bool { return self.l.length() + self.r.length() == 0; }
}

function min(a: int, b: int) -> int {
    if (a < b) { return a; }
    return b;
}

function add_edge(by: int, to: int, cap: int, cost: int, edges: Edge[], head: int[]) {
    edges.push(new Edge { to: to, next: edges.length() + 2, cap: cap, cost: cost });
	head[by] = edges.length() + 1;
}

function add(u: int, v: int, cap: int, cost: int, edges: Edge[], head: int[]) {
	add_edge(u, v, cap, cost, edges, head);
    add_edge(v, u, 0, -cost, edges, head);
}

function spfa(n: int, s: int, t: int, pre: int[], vis: int[], c: int[], edges: Edge[], head: int[]) -> bool {
    for (let i = 1; i <= n; i += 1) { pre[i] = -1; vis[i] = 0; c[i] = 1000000000000000000; }
    let q = new Queue { l: [], r: [] };
	q.push(s);
    vis[s] = 1; c[s] = 0;
	while (!q.empty()) {
		let u = q.pop();
        vis[u] = 0;
		for (let i = head[u]; i != 0; i = edges[i].next) {
			let v = edges[i].to;
			if (edges[i].cap > 0 && c[v] > c[u] + edges[i].cost) {
				c[v] = c[u] + edges[i].cost;
				pre[v] = i;
                if (vis[v] != 0) {
                    vis[v] = 1;
                    q.push(v);
                }
			}
		}
    }
	return pre[t] != -1;
}

function mcmf(n: int, s: int, t: int, pre: int[], vis: int[], c: int[], edges: Edge[], head: int[]) -> int {
	let max_flow = 0;
	let min_cost = 0;
	while (spfa(n, s, t, pre, vis, c, edges, head)) {
		let x = t;
        let flow = 1000000000;
        while (x != s) { flow = min(flow, edges[pre[x]].cap); x = edges[pre[x] ^ 1].to; }
		max_flow += flow;
        x = t;
        min_cost += c[t] * flow;
		while (x != s) {
			edges[pre[x]].cap -= flow;
			edges[pre[x] ^ 1].cap += flow;
			x = edges[pre[x] ^ 1].to;
		}
    }
	return min_cost;
}