Minimum Cost Maximum Flow

Quick Revisit
USE WHEN: Optimal assignment, transportation, or any max-flow problem where edges also have per-unit costs
INVARIANT: At each step, augment along the shortest (minimum-cost) path in the residual graph — guarantees global minimum cost at max flow
TIME: O(F × E log V) with Dijkstra + potentials, O(F × VE) with SPFA | SPACE: O(V + E)
CLASSIC BUG: Using Dijkstra without Johnson's potentials on a graph with negative-cost residual edges — produces wrong shortest paths
PRACTICE: 05-ladder-graphs

Given a directed graph where each edge has a capacity and a cost per unit of flow, find the maximum flow from source $s$ to sink $t$ that has the minimum total cost among all maximum flows.

Difficulty: [Advanced]Prerequisites: Max Flow (Dinic's), Bellman-Ford, DijkstraCF Rating: 1900-2100 ID: AL-27

Intuition

"Assign $N$ workers to $N$ jobs. Each worker-job pair has a cost. Find a minimum-cost perfect matching."

With $N = 3$ workers ${W_{1}, W_{2}, W_{3}}$ and jobs ${J_{1}, J_{2}, J_{3}}$ :

         J1   J2   J3
   W1  [  3    8    5 ]
   W2  [  4    2    7 ]
   W3  [  6    5    1 ]

A brute-force approach enumerates all $N!$ permutations:

W1->J1, W2->J2, W3->J3 : 3 + 2 + 1 = 6   <-- optimal
W1->J1, W2->J3, W3->J2 : 3 + 7 + 5 = 15
W1->J2, W2->J1, W3->J3 : 8 + 4 + 1 = 13
W1->J2, W2->J3, W3->J1 : 8 + 7 + 6 = 21
W1->J3, W2->J1, W3->J2 : 5 + 4 + 5 = 14
W1->J3, W2->J2, W3->J1 : 5 + 2 + 6 = 13

Six permutations is manageable. But $N! = 20!$ is already $\approx 2.4 \times 10^{18}$ -- hopelessly slow.

We need a way to find the cheapest assignment without trying every permutation.

"Model as a flow network where edges have both capacity and cost. Find augmenting paths that are cheapest (shortest path), not just any path."

In standard max flow, we use BFS to find any augmenting path. For min-cost flow, we replace BFS with a shortest path algorithm. The recommended choice is Dijkstra with Johnson's potentials -- it runs in $O (E \log V)$ per augmentation and always terminates. Bellman-Ford / SPFA also works (and is what most short templates ship with), but on adversarial graphs SPFA can degrade to $O (V E)$ per iteration. For contest robustness, prefer Dijkstra+potentials; SPFA is the simpler fallback when you do not need worst-case guarantees.

Why does cheapest-first work? Suppose we have pushed $k$ units of flow at minimum cost. The next unit should travel along the cheapest remaining $s$ - $t$ path in the residual graph. Residual back-edges carry negative cost (refunding the cost of flow they cancel), so the algorithm can undo expensive earlier decisions. This greedy-by-cost strategy is provably optimal.

Visual Walkthrough -- a rerouting example

The cleanest illustration of why MCMF needs back edges is a problem where the naive greedy assignment is suboptimal and the algorithm must un-assign an earlier choice. The standard 3x3 sorted example does not exercise that path; here is one that does.

Three workers ${W_{1}, W_{2}, W_{3}}$ , three jobs ${J_{1}, J_{2}, J_{3}}$ (each capacity 1):

         J1   J2   J3
   W1  [  1   10   10 ]
   W2  [  4   10    5 ]
   W3  [ 10    3   10 ]

A naive greedy that assigns each worker their own cheapest job picks:

$W_{1} \to J_{1}$ at cost 1
$W_{2} \to J_{3}$ at cost 5
$W_{3} \to J_{2}$ at cost 3

Total = 9. That is also optimal. But what if SSP runs in this order?

Iteration 1. Cheapest $s \to t$ path: $s \to W_{1} \to J_{1} \to t$ (cost $1$ ). Push 1. Total cost = 1. Residual now has back edge $J_{1} \to W_{1}$ with cost $- 1$ .

Iteration 2. Cheapest path: $s \to W_{3} \to J_{2} \to t$ (cost $3$ ). Push 1. Total cost = 4. Back edge $J_{2} \to W_{3}$ cost $- 3$ .

Iteration 3. Cheapest path?

Direct: $s \to W_{2} \to J_{3} \to t$ at cost $0 + 5 + 0 = 5$ .
Via reroute: $s \to W_2 \to J_1 \to W_1_\text{back} \to ?$ requires another job for $W_{1}$ , all of $W_{1}$ 's remaining costs are 10 -- not cheaper.

Push direct: 1 unit at cost 5. Total = 9. No rerouting was needed.

Now perturb the matrix to make rerouting required. Change $c (W_{2}, J_{3})$ to 100:

         J1   J2   J3
   W1  [  1   10  100 ]
   W2  [  4   10  100 ]
   W3  [ 10    3   10 ]

Naive worker-by-worker greedy: $W_{1} \to J_{1}$ (1), $W_{2} \to ?$ (cheapest free is $J_{2}$ at 10), $W_{3} \to J_{3}$ (10). Total = 21.

But the true optimum routes through $W_{1}$ 's back edge:

$W_{2} \to J_{1}$ (cost 4), then $W_{1}$ takes $J_{2}$ (cost 10), $W_{3}$ takes $J_{3}$ (cost 10) -- total = 24.
Or: $W_{1} \to J_{1}$ (1), $W_{3} \to J_{2}$ (3), $W_{2} \to J_{3}$ (100) -- total = 104.
Or: $W_{1} \to J_{1}$ (1), $W_{2} \to J_{2}$ (10), $W_{3} \to J_{3}$ (10) -- total = 21.

Let me trace SSP and watch it find a rerouting path:

Iteration 1. Cheapest: $s \to W_{1} \to J_{1} \to t$ , cost 1. Total = 1.

Iteration 2. Cheapest: $s \to W_{3} \to J_{2} \to t$ , cost 3. Total = 4.

Iteration 3. $W_{2}$ needs to route. Direct options:

$s \to W_{2} \to J_{3} \to t$ at cost 100.
$s \to W_2 \to J_1 \to W_1_\text{back} \to J_2 \to W_3_\text{back} \to ?$ -- dead end (no remaining job for $W_{3}$ that is cheap).
$s \to W_2 \to J_2 \to W_3_\text{back} \to J_3 \to t$ -- this reroutes. Cost: $0 + 10 + (- 3) + 10 + 0 = 17$ .

Pick the rerouting path at cost 17, not the direct 100. Total = 4 + 17 = 21.

Net effect of the residual reroute:

$W_{2}$ ends up assigned to $J_{2}$ (cost 10).
$W_{3}$ swaps from $J_{2}$ to $J_{3}$ (refund 3, pay 10, net +7).
The "+10 + (-3) + 10" arithmetic in the path cost is exactly the assignment swap.

That is the rerouting story: an earlier "cheapest-first" assignment ( $W_{3} \to J_{2}$ ) is silently undone by the third augmenting path, and the back edge $J_{2} \to W_{3}$ with negative cost is the bookkeeping that makes the global cost $21$ , not $4 + 100 = 104$ .

For completeness, a clean visualisation of the original (non-rerouting) trace on the simpler matrix follows; it is useful for sanity-checking the implementation even though it does not stress the back-edge logic.

Model the 3-worker 3-job example as a flow network. Create a source $s$ , a sink $t$ , and bipartite edges with capacity 1 and cost equal to the assignment cost.

                       cap=1, cost=3
          +------[W1]---------->[J1]------+
          |        |  \___               |
   cap=1  |  cap=1 |      \__cost=5      | cap=1
   cost=0 |  cost=0|         \___         | cost=0
          |        |             v        |
   [s]----+------[W2]--cost=2->[J2]------+----[t]
          |        |             ^        |
   cap=1  |  cap=1 |         ___/         | cap=1
   cost=0 |  cost=0|    ___/cost=5        | cost=0
          |        |  /                   |
          +------[W3]--cost=1-->[J3]------+
                   (+ other cross-edges omitted for clarity)

Each $s \to W_{i}$ edge has capacity 1, cost 0. Each $J_{j} \to t$ edge has capacity 1, cost 0. Each $W_{i} \to J_{j}$ edge has capacity 1, cost = $c_{i j}$ .

Iteration 1: Find shortest $s$ - $t$ path in residual graph (by cost).

Shortest path: s -> W3 -> J3 -> t   (cost = 0 + 1 + 0 = 1)
Push 1 unit. Total flow = 1, total cost = 1.

Residual updates:
  W3 -> J3 : cap 1->0 (saturated)
  J3 -> W3 : back-edge created, cap 0->1, cost = -1

Iteration 2: Shortest path in updated residual graph.

Shortest path: s -> W2 -> J2 -> t   (cost = 0 + 2 + 0 = 2)
Push 1 unit. Total flow = 2, total cost = 1 + 2 = 3.

Residual updates:
  W2 -> J2 : cap 1->0 (saturated)
  J2 -> W2 : back-edge created, cap 0->1, cost = -2

Iteration 3: Shortest path in updated residual graph.

Shortest path: s -> W1 -> J1 -> t   (cost = 0 + 3 + 0 = 3)
Push 1 unit. Total flow = 3, total cost = 3 + 3 = 6.

All $s$ -edges saturated. Maximum flow = 3, minimum cost = 6.

This matches the optimal brute-force assignment $W_{1} \to J_{1}, W_{2} \to J_{2}, W_{3} \to J_{3}$ .

  SUCCESSIVE SHORTEST PATHS -- cost grows monotonically:

  Iteration:     1          2          3
  Path cost:     1          2          3
  Cumulative:    1          3          6  (optimal!)

  +------+------+------+
  |      |      |      |  Each bar = cost of one
  |      |      |  3   |  augmenting path.
  |      |  2   |  2   |
  |  1   |  1   |  1   |  Paths are found in
  +------+------+------+  INCREASING cost order.
  iter 1  iter 2  iter 3

  If we'd picked a costlier path first (say cost 7),
  the back edges would let us undo it later --
  but cheapest-first avoids that detour entirely.

The Invariant

At every step, the flow found so far has minimum cost among all flows of that value.

After pushing $k$ augmenting paths, the total flow is $k$ and its cost is the minimum possible for flow value $k$ . This holds because each augmenting path is the shortest (cheapest) path in the current residual graph, and negative-cost back-edges allow correction of earlier decisions.

When to Reach for This

Trigger phrases:

"Assignment problem" / "minimum cost matching"
"Flow with costs" / "cheapest way to route"
"Min-cost bipartite matching"
"Transportation problem"
"Minimum cost to satisfy demands"
Any max-flow problem where edges have costs and you must minimize total cost

Scale guidance: MCMF is practical for $V \leq 500$ , $E \leq 5000$ in competitive programming. For pure assignment ( $N \leq 500$ ), the Hungarian algorithm ( $O (N^{3})$ ) is faster, but MCMF is more versatile.

What the Code Won't Teach You

MCMF is max flow's quieter, harder sibling. The code structure is nearly identical -- add edges, find augmenting paths, push flow. The crucial difference is invisible in the code: each augmenting path must be the cheapest path, not just any path. This means replacing BFS with SPFA or Dijkstra+potentials. The code change is small; the conceptual shift is large.

The back-edge cost is the refund mechanism. In plain max flow, back edges let you undo flow. In MCMF, back edges let you undo flow and recoup its cost. A back edge with cost $- c$ means "if you cancel one unit of flow on this edge, you get $c$ refunded." This is why the algorithm can correct expensive early decisions -- it literally gets its money back through negative-cost back edges.

  COST FLOW ON BACK EDGES -- the refund:

  Forward edge (W1->J2, cap=1, cost=8):
    "Assign W1 to J2, costs 8"

  After pushing 1 unit:
    Forward: (W1->J2, cap=0, cost=8)   [saturated]
    Back:    (J2->W1, cap=1, cost=-8)   [undo option]

  Later augmenting path uses the back edge:
    ... -> J2 -> W1 -> J1 -> ...  (cost includes -8)

  Net effect: W1 reassigned from J2 to J1
              Refund 8, pay cost(W1->J1) = 3
              Net savings: 5

Know when NOT to use MCMF. For pure assignment ( $N \leq 300$ ), the Hungarian algorithm is $O (N^{3})$ and simpler. For max-flow-only (no costs), plain Dinic's is faster. MCMF is the right tool when you need both maximum flow and minimum cost -- and the graph has general structure, not just bipartite.

Theory

Successive Shortest Paths

The core algorithm:

Initialize zero flow.
While an augmenting $s \to t$ path exists in the residual graph: a. Find the shortest (minimum cost) $s \to t$ path using SPFA or Dijkstra with potentials. b. Push the maximum possible flow along this path (bottleneck capacity). c. Update residual capacities and costs (back-edges get negative cost).
Return (total flow, total cost).

Why we prefer Dijkstra with Johnson's potentials. SPFA has worst-case $O (V E)$ per iteration and there are well-known graphs that hit the worst case. Maintaining Johnson's potentials $h [v]$ lets us reduce all edge weights to non-negative and run Dijkstra ( $O (E \log V)$ per iteration). The potentials are updated after each shortest-path computation using the distances found. This is the contest-robust default for MCMF.

Why SPFA / Bellman-Ford still appears in templates. Residual graphs contain negative-cost edges (back-edges). Dijkstra cannot handle negative edges directly, so a one-line SPFA implementation is shorter. Use SPFA when (a) you only need correctness on small inputs and (b) you do not want to maintain potentials. Be aware that adversarial test data on harder problems can TLE pure SPFA.

Reduced cost with Johnson's potentials

Define potential $h [v]$ for each vertex. For an edge $(u, v)$ with cost $w$ , the reduced cost is:

w^{'} (u, v) = w (u, v) + h [u] - h [v]

If $h$ satisfies $h [v] \leq h [u] + w (u, v)$ for all residual edges $(u, v)$ (i.e., $h$ is a valid shortest-path distance), then $w^{'} (u, v) \geq 0$ for all residual edges. This lets us run Dijkstra on reduced costs.

After each Dijkstra run with distances $d [v]$ , update: $h [v] \leftarrow h [v] + d [v]$ .

Initial potentials: Run one Bellman-Ford from $s$ on the original graph to get $h [v] = dist (s, v)$ . If all original costs are non-negative, simply set $h [v] = 0$ initially and use the first Dijkstra run to establish potentials.

Complexity

Variant	Per-iteration	Total
SPFA-based	$O (V E)$	$O (F V E)$ where $F$ = max flow value
Dijkstra + potentials	$O (E \log V)$	$O (F E \log V)$

For unit-capacity graphs (like assignment), $F \leq V$ , so Dijkstra variant is $O (V E \log V)$ .

  JOHNSON'S POTENTIALS -- eliminating negative edges:

  Original edge (u->v): cost = w
  Reduced cost:        w' = w + h[u] - h[v]

  If h[v] <= h[u] + w for all edges (valid potential):
    w' = w + h[u] - h[v] >= 0   <- non-negative!

  After each Dijkstra with distances d[]:
    h[v] <- h[v] + d[v]    (update potentials)

  +-- Before potentials --+   +-- After potentials ---+
  |  u --(-3)--> v        |   |  u --(0)--> v         |
  |  (negative cost!)     |   |  w' = -3 + h[u]-h[v]  |
  |  Dijkstra FAILS here  |   |  = -3 + 0 - (-3) = 0  |
  +------------------------+   |  Dijkstra works!       |
                               +------------------------+

Implementation

Version 1: SPFA-based MCMF (Contest Template)

cpp

#include <bits/stdc++.h>
using namespace std;

struct MCMF {
    struct Edge {
        int to, rev;
        long long cap, cost;
    };

    int n;
    vector<vector<Edge>> g;
    vector<long long> dist;
    vector<int> prevv, preve;
    vector<bool> in_queue;

    MCMF(int n) : n(n), g(n), dist(n), prevv(n), preve(n), in_queue(n) {}

    void add_edge(int from, int to, long long cap, long long cost) {
        g[from].push_back({to, (int)g[to].size(), cap, cost});
        g[to].push_back({from, (int)g[from].size() - 1, 0, -cost});
    }

    bool spfa(int s, int t) {
        fill(dist.begin(), dist.end(), numeric_limits<long long>::max());
        fill(in_queue.begin(), in_queue.end(), false);
        dist[s] = 0;
        deque<int> q;
        q.push_back(s);
        in_queue[s] = true;
        while (!q.empty()) {
            int v = q.front(); q.pop_front();
            in_queue[v] = false;
            for (int i = 0; i < (int)g[v].size(); i++) {
                auto& e = g[v][i];
                if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[v] + e.cost;
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    if (!in_queue[e.to]) {
                        // SLF optimization: push to front if dist is small
                        if (!q.empty() && dist[e.to] < dist[q.front()])
                            q.push_front(e.to);
                        else
                            q.push_back(e.to);
                        in_queue[e.to] = true;
                    }
                }
            }
        }
        return dist[t] < numeric_limits<long long>::max();
    }

    // Returns {max_flow, min_cost}.
    // Set flow_limit to cap total flow (e.g., for partial flow problems).
    pair<long long, long long> min_cost_flow(int s, int t,
                                              long long flow_limit = LLONG_MAX) {
        long long flow = 0, cost = 0;
        while (flow < flow_limit && spfa(s, t)) {
            long long d = flow_limit - flow;
            for (int v = t; v != s; v = prevv[v])
                d = min(d, g[prevv[v]][preve[v]].cap);

            flow += d;
            cost += d * dist[t];

            for (int v = t; v != s; v = prevv[v]) {
                g[prevv[v]][preve[v]].cap -= d;
                g[v][g[prevv[v]][preve[v]].rev].cap += d;
            }
        }
        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;
    MCMF mcmf(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap, cost;
        cin >> u >> v >> cap >> cost;
        u--; v--;
        mcmf.add_edge(u, v, cap, cost);
    }
    auto [flow, cost] = mcmf.min_cost_flow(s, t);
    cout << flow << " " << cost << "\n";
    return 0;
}

Version 2: Dijkstra + Johnson's Potentials (Faster Template)

cpp

#include <bits/stdc++.h>
using namespace std;

struct MCMF {
    struct Edge {
        int to, rev;
        long long cap, cost;
    };

    int n;
    vector<vector<Edge>> g;
    vector<long long> h, dist;  // h = Johnson's potentials
    vector<int> prevv, preve;

    MCMF(int n) : n(n), g(n), h(n, 0), dist(n), prevv(n), preve(n) {}

    void add_edge(int from, int to, long long cap, long long cost) {
        g[from].push_back({to, (int)g[to].size(), cap, cost});
        g[to].push_back({from, (int)g[from].size() - 1, 0, -cost});
    }

    // Run Dijkstra on reduced costs. Returns true if t is reachable.
    bool dijkstra(int s, int t) {
        fill(dist.begin(), dist.end(), numeric_limits<long long>::max());
        priority_queue<pair<long long, int>,
                       vector<pair<long long, int>>,
                       greater<>> pq;
        dist[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d > dist[v]) continue;
            for (int i = 0; i < (int)g[v].size(); i++) {
                auto& e = g[v][i];
                if (e.cap <= 0) continue;
                // Reduced cost: e.cost + h[v] - h[e.to]
                long long nd = dist[v] + e.cost + h[v] - h[e.to];
                if (nd < dist[e.to]) {
                    dist[e.to] = nd;
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    pq.push({nd, e.to});
                }
            }
        }
        return dist[t] < numeric_limits<long long>::max();
    }

    // Initialize potentials via Bellman-Ford (needed if graph has negative costs).
    // Skip this if all original edge costs are >= 0.
    void init_potentials(int s) {
        fill(h.begin(), h.end(), numeric_limits<long long>::max());
        h[s] = 0;
        for (int iter = 0; iter < n - 1; iter++) {
            for (int v = 0; v < n; v++) {
                if (h[v] == numeric_limits<long long>::max()) continue;
                for (auto& e : g[v]) {
                    if (e.cap > 0 && h[v] + e.cost < h[e.to])
                        h[e.to] = h[v] + e.cost;
                }
            }
        }
    }

    pair<long long, long long> min_cost_flow(int s, int t,
                                              long long flow_limit = LLONG_MAX) {
        // Uncomment if graph has negative original costs:
        // init_potentials(s);

        long long flow = 0, cost = 0;
        while (flow < flow_limit && dijkstra(s, t)) {
            // Update potentials: real dist = reduced dist + h[to] - h[from]
            // New h[v] = h[v] + dist[v] ensures reduced costs stay non-negative
            for (int v = 0; v < n; v++) {
                if (dist[v] < numeric_limits<long long>::max())
                    h[v] += dist[v];
            }

            long long d = flow_limit - flow;
            for (int v = t; v != s; v = prevv[v])
                d = min(d, g[prevv[v]][preve[v]].cap);

            flow += d;
            // Real path cost = h[t] - h[s] after potential update
            cost += d * (h[t] - h[s]);

            for (int v = t; v != s; v = prevv[v]) {
                g[prevv[v]][preve[v]].cap -= d;
                g[v][g[prevv[v]][preve[v]].rev].cap += d;
            }
        }
        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;
    MCMF mcmf(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap, cost;
        cin >> u >> v >> cap >> cost;
        u--; v--;
        mcmf.add_edge(u, v, cap, cost);
    }
    auto [flow, cost] = mcmf.min_cost_flow(s, t);
    cout << flow << " " << cost << "\n";
    return 0;
}

Version 3: Explained SPFA Version

cpp

#include <bits/stdc++.h>
using namespace std;

struct MCMF {
    struct Edge {
        int to;       // destination vertex
        int rev;      // index of reverse edge in g[to]
        long long cap;   // residual capacity
        long long cost;  // cost per unit of flow
    };

    int n;
    vector<vector<Edge>> g;
    vector<long long> dist;   // shortest distance from source
    vector<int> prevv, preve; // previous vertex and edge index on shortest path
    vector<bool> in_queue;    // is vertex currently in the SPFA queue?

    MCMF(int n) : n(n), g(n), dist(n), prevv(n), preve(n), in_queue(n) {}

    // Add directed edge with given capacity and cost.
    // Reverse edge has capacity 0 and cost -cost (refund on cancellation).
    void add_edge(int from, int to, long long cap, long long cost) {
        g[from].push_back({to, (int)g[to].size(), cap, cost});
        g[to].push_back({from, (int)g[from].size() - 1, 0, -cost});
    }

    // SPFA: Bellman-Ford with deque optimization.
    // Finds shortest path from s to all vertices using cost as weight.
    // Only traverses edges with remaining capacity > 0.
    // Returns true if t is reachable.
    bool spfa(int s, int t) {
        fill(dist.begin(), dist.end(), numeric_limits<long long>::max());
        fill(in_queue.begin(), in_queue.end(), false);
        dist[s] = 0;
        deque<int> q;
        q.push_back(s);
        in_queue[s] = true;

        while (!q.empty()) {
            int v = q.front(); q.pop_front();
            in_queue[v] = false;

            for (int i = 0; i < (int)g[v].size(); i++) {
                auto& e = g[v][i];
                // Only consider edges with available capacity
                if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[v] + e.cost;
                    prevv[e.to] = v;  // remember how we got here
                    preve[e.to] = i;
                    if (!in_queue[e.to]) {
                        // SLF (Shortest Label First): if the new distance
                        // is smaller than the front, push to front
                        if (!q.empty() && dist[e.to] < dist[q.front()])
                            q.push_front(e.to);
                        else
                            q.push_back(e.to);
                        in_queue[e.to] = true;
                    }
                }
            }
        }
        return dist[t] < numeric_limits<long long>::max();
    }

    // Main MCMF routine.
    // Repeatedly finds cheapest augmenting path via SPFA, pushes flow.
    // flow_limit: upper bound on flow to push (default: unlimited).
    // Returns {total_flow, total_cost}.
    pair<long long, long long> min_cost_flow(int s, int t,
                                              long long flow_limit = LLONG_MAX) {
        long long flow = 0, cost = 0;

        while (flow < flow_limit && spfa(s, t)) {
            // Trace back the shortest path, find bottleneck capacity
            long long d = flow_limit - flow;
            for (int v = t; v != s; v = prevv[v])
                d = min(d, g[prevv[v]][preve[v]].cap);

            flow += d;
            cost += d * dist[t];  // dist[t] = cost of this shortest path

            // Update residual capacities along the path
            for (int v = t; v != s; v = prevv[v]) {
                g[prevv[v]][preve[v]].cap -= d;                   // forward edge
                g[v][g[prevv[v]][preve[v]].rev].cap += d;         // back edge
            }
        }
        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;
    MCMF mcmf(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap, cost;
        cin >> u >> v >> cap >> cost;
        u--; v--;
        mcmf.add_edge(u, v, cap, cost);
    }

    auto [total_flow, total_cost] = mcmf.min_cost_flow(s, t);
    cout << total_flow << " " << total_cost << "\n";
    return 0;
}

Operations Reference

Operation	Time	Space
Build graph (`add_edge` x $m$ )	$O (m)$	$O (V + E)$ -- each edge stores forward + reverse
Single SPFA call	$O (V E)$ worst case	$O (V + E)$
Single Dijkstra call (with potentials)	$O (E \log V)$	$O (V + E)$
MCMF via SPFA	$O (F \cdot V E)$	$O (V + E)$
MCMF via Dijkstra + potentials	$O (F \cdot E \log V)$	$O (V + E)$
Init potentials (Bellman-Ford)	$O (V E)$	$O (V)$
Assignment ( $N$ workers, $N$ jobs) via MCMF	$O (N^{3} \log N)$ Dijkstra variant	$O (N^{2})$

Here $F$ = total flow value, $V$ = vertices, $E$ = edges (including reverse edges).

Practical note: SPFA-based MCMF handles $V \leq 500$ , $E \leq 5000$ , $F \leq 500$ comfortably in 2-3 seconds on CF. The Dijkstra variant is ~2-5x faster in practice and preferred when all original costs are non-negative.

Problem Patterns

Pattern 1: Assignment Problem (Min-Cost Bipartite Matching)

Assign $N$ workers to $N$ jobs with minimum total cost. Classic MCMF application.

Construction:

Source $s$ connects to each worker $W_{i}$ with capacity 1, cost 0.
Each worker $W_{i}$ connects to each job $J_{j}$ with capacity 1, cost $c_{i j}$ .
Each job $J_{j}$ connects to sink $t$ with capacity 1, cost 0.

s --1,0--> W_i --1,c[i][j]--> J_j --1,0--> t

The max flow is $N$ (perfect matching); the min cost is the optimal assignment cost.

CF examples: CF 237E, CF 1572E

Pattern 2: Transportation / Supply-Demand

Nodes have supply (positive) or demand (negative). Ship goods along edges with per-unit costs to satisfy all demands at minimum cost.

Construction:

Create super-source $s$ , super-sink $t$ .
Supply node $v$ with supply $b_{v} > 0$ : edge $s \to v$ , capacity $b_{v}$ , cost 0.
Demand node $v$ with demand $| b_{v} |$ : edge $v \to t$ , capacity $| b_{v} |$ , cost 0.
Transport edge $(u, v)$ with capacity $c$ and cost $w$ : edge $u \to v$ , capacity $c$ , cost $w$ .
If max flow = total supply = total demand, all demands are met.

CF examples: CF 277E

Pattern 3: Min-Cost Flow on Grid / Matrix

Move objects on a grid from sources to destinations. Cost = distance moved. Model as flow network with grid cells as nodes.

Typical setup:

Each source cell connects to adjacent cells with capacity $\infty$ and cost 1 (or manhattan distance).
Or model directly as bipartite matching (sources vs destinations).

CF examples: CF 1187G

Pattern 4: K-Edge-Disjoint Shortest Paths

Find $K$ edge-disjoint paths from $s$ to $t$ minimizing total length. Directly solvable: set all edge capacities to 1, costs to edge lengths, flow limit to $K$ .

add_edge(u, v, 1, length[u][v])  for each edge
min_cost_flow(s, t, K)

CF examples: CF 1288F

Pattern 5: Time-Expanded Graphs

Model processes over time steps. Create copies of each node for each time step. Flow across time steps models waiting; flow between nodes models movement.

Useful for problems like "minimum cost to move $K$ agents from start to end over $T$ time steps."

CF examples: CF 818G

Pattern 6: Minimum Cost to Satisfy Constraints

General problems where you need to route flow to meet capacity or coverage constraints at minimum cost. Often involves creative modeling.

Recognizing the pattern: If the problem asks to minimize cost subject to:

Conservation constraints (flow in = flow out),
Capacity constraints (bounded usage of resources),
Total throughput requirement,

then MCMF is likely the right tool.

CF examples: CF 164C

Contest Cheat Sheet

+--------------------------------------------------------------+
|           MIN-COST MAX-FLOW CHEAT SHEET                      |
+--------------------------------------------------------------+
| WHEN TO USE:                                                 |
|   - Assignment / min-cost bipartite matching                 |
|   - Flow with per-edge costs                                 |
|   - Transportation / supply-demand networks                  |
|   - K edge-disjoint shortest paths                           |
|   - Grid movement with minimum total distance                |
+--------------------------------------------------------------+
| TEMPLATE (SPFA):                                             |
|   MCMF mcmf(n);                                             |
|   mcmf.add_edge(u, v, cap, cost);                           |
|   auto [flow, cost] = mcmf.min_cost_flow(s, t);             |
|   // Optional: mcmf.min_cost_flow(s, t, flow_limit);        |
+--------------------------------------------------------------+
| COMPLEXITY:                                                  |
|   SPFA:     O(F * V * E)        -- simple, handles negatives |
|   Dijkstra: O(F * E * log V)    -- faster, needs potentials  |
+--------------------------------------------------------------+
| NETWORK CONSTRUCTION:                                        |
|   - Each add_edge(u,v,cap,cost) auto-adds reverse(v,u,0,-c) |
|   - Source/sink edges: capacity = supply/demand, cost = 0    |
|   - Assignment: s->Wi cap=1 cost=0, Wi->Jj cap=1 cost=cij   |
|   -              Jj->t cap=1 cost=0                          |
+--------------------------------------------------------------+
| SPFA vs DIJKSTRA DECISION:                                   |
|   - All original costs >= 0  -->  Dijkstra (faster)          |
|   - Negative original costs  -->  SPFA or BF init + Dijkstra |
|   - Not sure / contest speed -->  SPFA (simpler, safe)       |
+--------------------------------------------------------------+
| GOTCHAS:                                                     |
|   - Reverse edge cost = -cost (NOT 0, unlike plain max flow) |
|   - cost accumulation: cost += d * dist[t], NOT d * e.cost   |
|   - Check flow_limit when you need partial flow, not max     |
|   - long long if costs * flow can exceed 2 * 10^9            |
+--------------------------------------------------------------+

Gotchas & Debugging

Reverse edge cost. In plain max flow, the reverse edge has capacity 0 and cost is irrelevant. In MCMF, the reverse edge must have cost $= - cost$ of the forward edge. This is what allows SPFA to "refund" cost when rerouting flow. Getting this wrong produces incorrect costs.

Cost accumulation. The cost of an augmenting path is dist[t] (shortest path distance), not the cost of individual edges summed manually. Accumulate as cost += d * dist[t] where d is the bottleneck flow pushed.

Negative cycles. If the residual graph has a negative-cost cycle, the shortest path is undefined. This should not happen in a correct MCMF formulation (Successive Shortest Paths prevents it), but if you see SPFA looping forever, check your network construction.

Infinite loop in SPFA. In rare cases with adversarial input, SPFA can be exponential. If you suspect TLE from SPFA, switch to the Dijkstra + potentials variant.

Cannot use Dijkstra directly with negative edge costs. If ANY edge has negative cost, Dijkstra gives wrong shortest paths. Solutions:

Johnson's potentials: Run Bellman-Ford once to get potentials h[v]. Reweight: w'(u,v) = w(u,v) + h[u] - h[v] >= 0. Update potentials after each iteration.
Use SPFA/Bellman-Ford as the shortest-path subroutine instead of Dijkstra.

After the first Bellman-Ford, subsequent iterations can use Dijkstra with updated potentials (the residual graph has non-negative reduced costs). This gives O(F * E log V) total.

Partial flow. Sometimes you want minimum cost for exactly $K$ units of flow, not the maximum flow. Use flow_limit = K. If the max flow is less than $K$ , the problem may be infeasible.

Integer overflow. Costs are multiplied by flow amounts. If max cost per edge is $10^{6}$ and max flow is $10^{5}$ , total cost can reach $10^{11}$ -- use long long throughout.

0-index vs 1-index. Same as max flow -- off-by-one on vertex numbering is common. The number of nodes must include $s$ and $t$ if they are virtual nodes added for the construction.

Debugging flow decomposition. After running MCMF, verify:

Total flow out of $s$ = total flow into $t$ = returned flow value.
For each edge: $0 \leq flow \leq original capacity$ (flow = original cap $-$ residual cap).
For each non-source, non-sink vertex: flow in = flow out.
Total cost = $\sum_{edges} flow (e) \times cost (e)$ .

TLE tips.

SPFA is fine for $V \leq 500$ , $E \leq 5000$ , $F \leq 500$ .
Switch to Dijkstra + potentials for larger graphs.
Avoid $O (V^{2})$ edges when $O (V)$ suffices (e.g., chain edges instead of all-pairs).

Mental Traps

Trap 1: "Min cost flow = max flow + pick the cheapest one."

These are different problems. "Min cost max flow" finds the cheapest way to achieve maximum flow. "Min cost flow of exactly $k$ units" finds the cheapest way to push exactly $k$ units (which may be less than the max flow). Many contest problems want the second, and using the first gives WA because you overshoot.

  TWO DIFFERENT PROBLEMS:

  Problem A: "Min cost MAX flow"         Problem B: "Min cost flow of k units"
  +--------------------------------+     +----------------------------------+
  | Push as much flow as possible  |     | Push exactly k units             |
  | Among all max flows, pick the  |     | Among all flows of value k,      |
  | one with minimum total cost    |     | pick the cheapest                |
  +--------------------------------+     +----------------------------------+
  | flow_limit = infinity          |     | flow_limit = k                   |
  | Cost might be high but flow    |     | May stop before max flow         |
  | is maximized first             |     | if k < max_flow                  |
  +--------------------------------+     +----------------------------------+

Trap 2: "SPFA is always safe for shortest paths with negative edges."

SPFA has worst-case $O (V E)$ per call. In MCMF, you call it $O (F)$ times (once per augmenting path). Total: $O (F \cdot V E)$ . For $F = V = 500, E = 5000$ , that's $1.25 \times 10^{9}$ -- borderline TLE. Dijkstra with Johnson's potentials drops this to $O (F \cdot E \log V) \approx 3 \times 10^{7}$ . When the time limit is tight, SPFA-based MCMF fails and Dijkstra+potentials passes.

  WHEN SPFA HITS THE WALL:

  V=500, E=5000, F=500

  SPFA:     500 x 500 x 5000 = 1.25 x 10⁹   <- TLE risk
  Dijkstra: 500 x 5000 x 13  = 3.25 x 10⁷   <- safe

  Rule of thumb:
    V <= 200, E <= 2000  -> SPFA is fine
    V <= 500, E <= 5000  -> Use Dijkstra + potentials
    Negative original costs? -> Init potentials with BF first

Common Mistakes

Reverse edge cost not negated. MCMF returns correct max flow but the total cost is negative despite all-positive edge costs. The cause: reverse edges have cost $+ c$ instead of $- c$ . Pushing flow back along a reverse edge adds cost instead of refunding it, causing the algorithm to under-report flow and produce nonsensical cost values. Always: forward edge cost $= c$ , reverse edge cost $= - c$ .

Debug Drills

Drill 1 -- Reverse edge cost not negated

cpp

void add_edge(int u, int v, int cap, int cost) {
    edges.push_back({v, cap, cost});
    edges.push_back({u, 0, cost});  // BUG: should be -cost
}

What's wrong?

Reverse edges must have negated cost so that canceling flow along a forward edge refunds the cost:

cpp

edges.push_back({u, 0, -cost});

Drill 2 -- Dijkstra without potentials on negative edges

cpp

// Using Dijkstra directly for MCMF
auto [dist, parent] = dijkstra(s);  // BUG: graph has negative-cost reverse edges

What's wrong?

Reverse edges have negative costs, and Dijkstra doesn't handle negative edge weights. Either use SPFA/Bellman-Ford, or apply Johnson's potentials to make all reduced costs non-negative:

cpp

// After initial Bellman-Ford for potentials h[]:
reduced_cost(u, v) = cost(u, v) + h[u] - h[v];  // >= 0
// Now Dijkstra works

Drill 3 -- Not updating potentials after each augmentation

cpp

// After running Dijkstra with potentials:
augment_along_shortest_path();
// Missing: update h[v] += dist[v] for all v

What's wrong?

After each augmentation, the residual graph changes. Potentials must be updated as h[v] += dist[v] (where dist[v] is the shortest-path distance from the last Dijkstra run) to maintain the invariant that reduced costs are non-negative:

cpp

for (int v = 0; v < n; v++)
    h[v] += dist[v];

Self-Test

Before moving on, verify you can answer these without looking at the notes:

[ ] State why Dijkstra fails directly on the residual graph -- negative back-edge costs violate the non-negative weight requirement.
[ ] Explain Johnson's potential reweighting -- how h[] is maintained, what reduced costs are, and why they are non-negative after the first SPFA.
[ ] Write the SPFA-based min-cost flow from memory -- including the cap > 0 guard and back-edge cost negation.
[ ] Model a min-cost bipartite matching as min-cost flow -- what nodes, edges, capacities, and costs to use.
[ ] State the difference between min-cost max-flow and min-cost flow of exactly k units -- and how flow_limit enforces the latter.
[ ] Explain why the Successive Shortest Paths algorithm produces an optimal solution -- each augmenting path is cheapest in the residual graph, and back-edges allow correction of earlier decisions.
[ ] Decide when to use SPFA vs Dijkstra with potentials -- SPFA is simpler and handles negatives; Dijkstra is faster but needs potential maintenance.

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Understand flow with costs conceptually.
1500	Know that MCMF exists and when to apply it; use a template for direct problems.
1800	Implement SPFA-based MCMF from scratch; model assignment and transportation problems as cost-flow networks.
2100	Use Johnson's potentials for Dijkstra-based MCMF; handle problems with $10^{4}$ + nodes by exploiting network structure.

#	Problem	Source	Difficulty	Key Idea
1	Minimum Cost Flow	CSES	Medium	Direct MCMF template check
2	CF 237E	CF 1700	Medium	Assignment problem on a graph
3	CF 277E	CF 2100	Medium	Transportation / supply-demand
4	CF 164C	CF 2100	Medium	Min-cost flow with constraints
5	CF 1187G	CF 2400	Hard	Grid rearrangement via MCMF
6	CF 1288F	CF 2400	Hard	K disjoint shortest paths
7	CF 818G	CF 2500	Hard	Time-expanded flow network
8	CF 1572E	CF 2500	Hard	Matching with cost optimization
9	CF 1061E	CF 2200	Medium	Min-cost flow modeling
10	SPOJ MCMF	SPOJ	Medium	Classic MCMF template problem

Minimum Cost Maximum Flow ​

Intuition ​

Visual Walkthrough -- a rerouting example ​

The Invariant ​

When to Reach for This ​

What the Code Won't Teach You ​

Theory ​

Successive Shortest Paths ​

Reduced cost with Johnson's potentials ​

Complexity ​

Implementation ​

Version 1: SPFA-based MCMF (Contest Template) ​

Version 2: Dijkstra + Johnson's Potentials (Faster Template) ​

Version 3: Explained SPFA Version ​

Operations Reference ​

Problem Patterns ​

Pattern 1: Assignment Problem (Min-Cost Bipartite Matching) ​

Pattern 2: Transportation / Supply-Demand ​

Pattern 3: Min-Cost Flow on Grid / Matrix ​

Pattern 4: K-Edge-Disjoint Shortest Paths ​

Pattern 5: Time-Expanded Graphs ​

Pattern 6: Minimum Cost to Satisfy Constraints ​

Contest Cheat Sheet ​

Gotchas & Debugging ​

Mental Traps ​

Common Mistakes ​

Debug Drills ​

Self-Test ​

Practice Problems ​

Further Reading ​

Minimum Cost Maximum Flow

Intuition

Visual Walkthrough -- a rerouting example

The Invariant

When to Reach for This

What the Code Won't Teach You

Theory

Successive Shortest Paths

Reduced cost with Johnson's potentials

Complexity

Implementation

Version 1: SPFA-based MCMF (Contest Template)

Version 2: Dijkstra + Johnson's Potentials (Faster Template)

Version 3: Explained SPFA Version

Operations Reference

Problem Patterns

Pattern 1: Assignment Problem (Min-Cost Bipartite Matching)

Pattern 2: Transportation / Supply-Demand

Pattern 3: Min-Cost Flow on Grid / Matrix

Pattern 4: K-Edge-Disjoint Shortest Paths

Pattern 5: Time-Expanded Graphs

Pattern 6: Minimum Cost to Satisfy Constraints

Contest Cheat Sheet

Gotchas & Debugging

Mental Traps

Common Mistakes

Debug Drills

Self-Test

Practice Problems

Further Reading