⚙️AlgorithmAdvanced

Minimum Cost Maximum Flow

Key Points

  • •
    Minimum Cost Maximum Flow (MCMF) finds the maximum possible flow from a source to a sink while minimizing the total cost paid per unit of flow along edges.
  • •
    It repeatedly sends flow along the currently cheapest augmenting path in the residual graph (successive shortest augmenting path).
  • •
    Using potentials (Johnson’s reweighting) lets us run Dijkstra on non-negative reduced costs, yielding fast practical performance: typically O(F E log V).
  • •
    SPFA can handle negative costs directly but is slower in worst case: O(F V E), though it is simple and fine for small graphs.
  • •
    The assignment/transportation problems are special cases reducible to MCMF by building a bipartite flow network with unit capacities.
  • •
    Negative cost edges are safe if you initialize node potentials with Bellman–Ford (or SPFA) before running Dijkstra on reduced costs.
  • •
    Always add reverse edges with negative costs to form the residual graph; forgetting this breaks correctness and prevents canceling expensive choices.
  • •
    Use 64-bit (long long) for costs to avoid overflow when summing many edge costs or multiplying flow by cost.

Prerequisites

  • →Graph representations (adjacency lists) — MCMF is implemented on directed graphs with forward and reverse edges; you must understand how to store and traverse edges efficiently.
  • →Max flow and residual graphs — MCMF extends max flow; residual capacities and reverse edges are essential for augmenting and canceling flow.
  • →Shortest path algorithms (Dijkstra, Bellman–Ford, SPFA) — Successive shortest augmenting path requires computing cheapest paths, often under constraints like non-negative weights.
  • →Priority queues / heaps — Dijkstra’s algorithm depends on a min-priority queue for efficiency.
  • →Greedy algorithms and invariants — Understanding why picking the current cheapest path remains globally correct relies on maintaining reduced costs and potentials.
  • →Basic linear programming duality (optional) — Potentials correspond to dual variables; this perspective explains optimality and the non-existence of negative cycles.
  • →Integer arithmetic and overflow handling — Costs and distances can grow large; using 64-bit integers and safe infinities prevents bugs.

Detailed Explanation

Tap terms for definitions

01Overview

Minimum Cost Maximum Flow (MCMF) is a network flow algorithm that chooses not only how much flow to send from a source to a sink, but also which paths to use so that the total monetary (or other) cost is as small as possible. Each directed edge has a capacity (how much it can carry) and a per-unit cost (how expensive it is to use). The algorithm’s classic approach is the successive shortest augmenting path method: repeatedly find the cheapest s→t path in the current residual network and push as much flow as possible along it, updating residual capacities and reverse edges. This process continues until no more augmenting path exists (max flow reached) or a flow limit is met. Although finding a shortest path may be complicated by negative edge costs, a standard trick—node potentials (Johnson’s reweighting)—keeps reduced costs non-negative so Dijkstra’s algorithm can be used efficiently. Alternative strategies include SPFA-based shortest paths, cycle-canceling (find and eliminate negative-cost cycles), and scaling methods. MCMF is foundational for problems like assignment, transportation, min-cost k paths, and various scheduling or resource allocation tasks. Conceptually, MCMF unifies shortest paths and max-flow: it maximizes quantity while optimizing quality (cost) of the routing.

02Intuition & Analogies

Imagine shipping packages from a warehouse (source) to customers (sink) through a road network. Each road can carry only so many trucks per day (capacity), and each trip on that road costs fuel/toll money (cost per unit). If you only maximize the number of packages (max flow), you might take very long or expensive detours. If you only minimize cost for a single package (shortest path), you may ignore the need to serve everyone. Minimum Cost Maximum Flow balances both: it tries to move as many packages as possible while choosing routes that, on average, keep expenses down. Think of it like repeatedly picking the “cheapest viable route” given current congestion. After you send some trucks, roads fill up and the remaining best route may change. The residual network captures these dynamics: it not only shows remaining free lanes (forward residual capacity) but also allows “undoing” part of a previous choice (reverse edges with negative cost) if a new combination is globally cheaper—like rerouting some trucks to open a better plan. Potentials are mental price stickers on cities: when adjusted correctly, all adjusted road prices become non-negative, letting us safely use Dijkstra (which expects no negative edges) to quickly find the next cheapest route. Over time, this greedy yet globally aware process builds a shipping plan that moves the maximum number of packages for the lowest total bill.

03Formal Definition

A directed graph G = (V, E) has capacity 0 and cost per unit on each edge (u, v). A flow is a function f: E satisfying capacity constraints 0 and flow conservation at every node v V \{s, t\}: = . The value of the flow is = . The total cost is (f) = . In Minimum Cost Maximum Flow, the objective is to find a feasible flow f that maximizes and, among those with maximum value, minimizes (f) (lexicographic optimization). The successive shortest augmenting path algorithm operates on the residual graph , which has forward residual edges with capacity - and cost , and reverse residual edges with capacity and cost -. A node potential : V defines reduced costs = + (u) - (v). If all residual edges have 0, then shortest paths in correspond to shortest paths in original costs and allow efficient Dijkstra. Optimality is characterized by absence of negative-cost cycles in the residual graph; if none exist, the current flow is minimum cost for its value.

04When to Use

Use MCMF whenever you must route quantity under capacities but every unit has a price you want to minimize. Classic applications include: (1) Assignment problem: match n workers to n jobs with minimum total cost; build a bipartite flow network with unit capacities and edge costs equal to assignment costs. (2) Transportation/supply-demand: ship goods from multiple suppliers to consumers with different per-route shipping costs; attach a super-source/sink and connect supplies/demands. (3) Min-cost k disjoint (or capacity-limited) paths: send exactly k units of flow from s to t with minimum total path cost. (4) Project selection and scheduling with penalties/bonuses modeled as costs along edges. (5) Network design with per-edge usage fees where you also have capacity limits. Choose SPFA-based MCMF for small inputs or when implementation simplicity matters and performance is not critical. For larger graphs with possibly negative edges, use potentials with an initial Bellman–Ford (or SPFA) followed by repeated Dijkstra; this is the go-to for competitive programming in the 2000–2400 range. Consider specialized solvers (Hungarian algorithm) when the graph is dense and exactly matches the assignment structure for best asymptotic performance.

⚠️Common Mistakes

  • Forgetting reverse edges: MCMF relies on residual reverse edges with negative costs to allow canceling or rerouting previous choices. Always add a reverse edge for every forward edge with capacity 0 and cost = -cost.
  • Using Dijkstra directly on negative edges: If any residual edge can have negative cost, run Bellman–Ford (or SPFA) once to initialize potentials, then use Dijkstra on non-negative reduced costs.
  • Integer overflow: Total cost can exceed 32-bit range when summing many edges or multiplying by large flows. Store costs, distances, and total cost in 64-bit (long long).
  • Wrong infinity and distance updates: Use a safely large INF (e.g., LLONG_MAX/4) and guard against addition overflow when relaxing edges.
  • Not updating potentials correctly: After each Dijkstra, set \pi(v) := \pi(v) + dist(v) for all reachable v; leave others unchanged. This maintains non-negative reduced costs.
  • Mishandling flow limit vs. maximum flow: If you need exactly k units, stop when the sent flow reaches k; if you need max flow, keep augmenting until no path exists.
  • Building the assignment network incorrectly: Remember S→left nodes (cap=1), left→right edges (cap=1, cost=matrix[i][j]), right→T (cap=1). Off-by-one errors and index swaps are common.
  • Performance pitfalls: SPFA can be very slow on adversarial inputs; for larger constraints, prefer potentials + Dijkstra. Avoid O(VE) scans by using adjacency lists and priority queues.

Key Formulas

Total cost of a flow

Explanation: The total cost equals the sum over all edges of (flow on the edge) times (per-unit cost). This is the quantity MCMF tries to minimize among maximum flows.

Capacity constraints

Explanation: Flow on each edge cannot be negative and cannot exceed its capacity. These constraints define feasibility.

Flow conservation

Explanation: Except at source and sink, the amount of flow entering a node equals the amount leaving it. This preserves continuity of flow.

Reduced cost (Johnson reweighting)

Explanation: By assigning potentials to nodes, we transform edge costs to reduced costs. If all reduced costs in the residual graph are non-negative, we can safely run Dijkstra.

Potential update after Dijkstra

Explanation: After computing shortest distances with reduced costs, add these distances to the potentials. This maintains non-negative reduced costs in the next iteration.

SPFA-based complexity

Explanation: Each augmentation may take O(VE) in the worst case to find a shortest path, and we may do this up to F times, where F is the total flow sent.

Dijkstra with potentials complexity

Explanation: With non-negative reduced costs, each shortest path is found by Dijkstra in O(E log V) time (using a binary heap). This repeats up to F augmentations.

Negative-cycle optimality condition

Explanation: A flow is minimum cost for its value if and only if there are no negative-cost cycles in the residual graph. If one exists, pushing flow around it reduces total cost.

Linear programming form (primal)

Explanation: MCMF can be written as an LP: minimize linear cost subject to flow conservation (Af=b) and capacity bounds. Dual variables correspond to node potentials.

Summation identity (reference)

Explanation: Commonly used to estimate the number of relaxations or bounds in analyses; for example, repeated improvements that decrease a potential by at least 1 per step.

Complexity Analysis

Let V be the number of nodes, E the number of edges in the directed graph (counting each directed edge once), and F the total amount of flow sent (sum of augmentations). The successive shortest augmenting path (SSAP) framework repeats: find a minimum-cost path in the residual graph and augment along it. The bottleneck is the shortest path computation per augmentation. 1) SPFA-based MCMF: SPFA has a worst-case time O(VE) per shortest path. Over up to F augmentations, this yields O(F V E). Although SPFA is often fast on random or small inputs, adversarial graphs can force quadratic behavior per shortest path, making it unreliable for large constraints. 2) Dijkstra with potentials: If we maintain non-negative reduced costs using node potentials, each shortest path can be found with Dijkstra in O(E log V) time (binary heap). We need one initial Bellman–Ford (or SPFA) to set potentials if negative edges exist: O(VE). The total becomes O(VE + F E log V). In many competitive programming settings, this is effectively O(F E log V) and is significantly faster than SPFA. Space usage is O(V + E) for adjacency lists, plus O(V) for distances, potentials, parent pointers, and priority queue metadata; overall O(V + E). If we store both forward and reverse edges explicitly (standard), the constant factors roughly double E. Practical notes: F can be as large as O(min{out(s), in(t), sum of supplies}), and when capacities are integer, SSAP converges in at most F iterations (pushing at least 1 unit per time for unit capacities). Capacity scaling can reduce the number of augmentations by sending larger chunks first, improving constants in dense or high-capacity graphs.

Code Examples

Minimum Cost Maximum Flow with Dijkstra + Potentials (Johnson reweighting)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct MinCostMaxFlow {
5    struct Edge {
6        int to, rev;
7        long long cap, cost;
8    };
9
10    int n;
11    vector<vector<Edge>> g;
12
13    MinCostMaxFlow(int n): n(n), g(n) {}
14
15    void addEdge(int u, int v, long long cap, long long cost) {
16        Edge a{v, (int)g[v].size(), cap, cost};
17        Edge b{u, (int)g[u].size(), 0, -cost}; // reverse edge
18        g[u].push_back(a);
19        g[v].push_back(b);
20    }
21
22    pair<long long,long long> minCostMaxFlow(int s, int t, long long max_flow = (1LL<<60)) {
23        const long long INF = (1LL<<60);
24        long long flow = 0, cost = 0;
25        vector<long long> pot(n, 0);            // node potentials
26        vector<long long> dist(n);
27        vector<int> pv(n), pe(n);               // parent vertex and edge index
28
29        // If there are negative edge costs, initialize potentials by Bellman-Ford from s
30        // to ensure non-negative reduced costs for reachable nodes.
31        // This is optional if all costs >= 0.
32        {
33            vector<long long> d(n, INF);
34            d[s] = 0;
35            bool any = true;
36            for (int it = 0; it < n - 1 && any; ++it) {
37                any = false;
38                for (int u = 0; u < n; ++u) if (d[u] < INF) {
39                    for (auto &e : g[u]) if (e.cap > 0) {
40                        if (d[e.to] > d[u] + e.cost) {
41                            d[e.to] = d[u] + e.cost;
42                            any = true;
43                        }
44                    }
45                }
46            }
47            for (int v = 0; v < n; ++v) if (d[v] < INF) pot[v] = d[v];
48        }
49
50        while (flow < max_flow) {
51            // Dijkstra on reduced costs: w'(u,v) = cost + pot[u] - pot[v] >= 0
52            priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
53            fill(dist.begin(), dist.end(), INF);
54            dist[s] = 0;
55            pq.push({0, s});
56            while (!pq.empty()) {
57                auto [du, u] = pq.top(); pq.pop();
58                if (du != dist[u]) continue;
59                for (int i = 0; i < (int)g[u].size(); ++i) {
60                    auto &e = g[u][i];
61                    if (e.cap <= 0) continue;
62                    long long nd = du + e.cost + pot[u] - pot[e.to];
63                    if (nd < dist[e.to]) {
64                        dist[e.to] = nd;
65                        pv[e.to] = u; pe[e.to] = i;
66                        pq.push({nd, e.to});
67                    }
68                }
69            }
70            if (dist[t] == INF) break; // no more augmenting path -> max flow reached
71
72            // Update potentials: pi(v) += dist(v) for visited nodes
73            for (int v = 0; v < n; ++v) if (dist[v] < INF) pot[v] += dist[v];
74
75            // Find bottleneck capacity on the path
76            long long add = max_flow - flow;
77            for (int v = t; v != s; v = pv[v]) {
78                auto &e = g[pv[v]][pe[v]];
79                add = min(add, e.cap);
80            }
81
82            // Augment and accumulate real (original) cost
83            for (int v = t; v != s; v = pv[v]) {
84                auto &e = g[pv[v]][pe[v]];
85                auto &er = g[v][e.rev];
86                e.cap -= add;
87                er.cap += add;
88                cost += add * e.cost; // original cost (not reduced)
89            }
90            flow += add;
91        }
92        return {flow, cost};
93    }
94};
95
96int main() {
97    ios::sync_with_stdio(false);
98    cin.tie(nullptr);
99
100    // Example graph demonstrating negative edges handled via potentials
101    // Nodes: 0 (s), 3 (t)
102    int n = 4;
103    MinCostMaxFlow mcmf(n);
104
105    mcmf.addEdge(0, 1, 2, 1);   // s->1
106    mcmf.addEdge(0, 2, 1, 5);   // s->2
107    mcmf.addEdge(1, 2, 1, -2);  // negative cost edge
108    mcmf.addEdge(1, 3, 1, 2);   // 1->t
109    mcmf.addEdge(2, 3, 2, 1);   // 2->t
110
111    auto [flow, cost] = mcmf.minCostMaxFlow(0, 3);
112    cout << "Max flow: " << flow << "\n";
113    cout << "Min total cost: " << cost << "\n";
114
115    // Expected: flow = 3, cost = 9 (paths: 0-1-2-3 cost 0, 0-1-3 cost 3, 0-2-3 cost 6)
116    return 0;
117}
118

This implementation uses successive shortest augmenting paths with Johnson potentials. We optionally run Bellman–Ford once to handle negative original costs. Each iteration runs Dijkstra on non-negative reduced costs to find the cheapest residual path, augments along it, and updates potentials to keep reduced costs non-negative. The example demonstrates correctness with a negative-cost edge and prints the resulting max flow and minimum total cost.

Time: O(VE + F E log V) in general; effectively O(F E log V) when Dijkstra dominates.Space: O(V + E) for the graph and per-iteration arrays.
SPFA-based Minimum Cost Maximum Flow (simple, small constraints)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct MinCostMaxFlowSPFA {
5    struct Edge { int to, rev; int cap; long long cost; };
6    int n; vector<vector<Edge>> g;
7    MinCostMaxFlowSPFA(int n): n(n), g(n) {}
8
9    void addEdge(int u, int v, int cap, long long cost) {
10        Edge a{v, (int)g[v].size(), cap, cost};
11        Edge b{u, (int)g[u].size(), 0, -cost};
12        g[u].push_back(a); g[v].push_back(b);
13    }
14
15    pair<long long,long long> minCostMaxFlow(int s, int t, long long max_flow = (1LL<<60)) {
16        const long long INF = (1LL<<60);
17        long long flow = 0, cost = 0;
18        vector<long long> dist(n);
19        vector<int> inq(n), pv(n), pe(n);
20
21        while (flow < max_flow) {
22            fill(dist.begin(), dist.end(), INF);
23            fill(inq.begin(), inq.end(), 0);
24            queue<int> q;
25            dist[s] = 0; q.push(s); inq[s] = 1;
26            while (!q.empty()) {
27                int u = q.front(); q.pop(); inq[u] = 0;
28                for (int i = 0; i < (int)g[u].size(); ++i) {
29                    auto &e = g[u][i];
30                    if (e.cap <= 0) continue;
31                    if (dist[e.to] > dist[u] + e.cost) {
32                        dist[e.to] = dist[u] + e.cost;
33                        pv[e.to] = u; pe[e.to] = i;
34                        if (!inq[e.to]) { q.push(e.to); inq[e.to] = 1; }
35                    }
36                }
37            }
38            if (dist[t] == INF) break; // no path
39
40            // Bottleneck
41            int add = (int)min<long long>(max_flow - flow, INT_MAX);
42            for (int v = t; v != s; v = pv[v]) add = min(add, g[pv[v]][pe[v]].cap);
43
44            for (int v = t; v != s; v = pv[v]) {
45                auto &e = g[pv[v]][pe[v]];
46                auto &er = g[v][e.rev];
47                e.cap -= add; er.cap += add; cost += 1LL * add * e.cost;
48            }
49            flow += add;
50        }
51        return {flow, cost};
52    }
53};
54
55int main(){
56    ios::sync_with_stdio(false);
57    cin.tie(nullptr);
58
59    int n = 4; // 0(s), 3(t)
60    MinCostMaxFlowSPFA mcmf(n);
61
62    mcmf.addEdge(0, 1, 2, 1);
63    mcmf.addEdge(0, 2, 1, 5);
64    mcmf.addEdge(1, 2, 1, -2);
65    mcmf.addEdge(1, 3, 1, 2);
66    mcmf.addEdge(2, 3, 2, 1);
67
68    auto [flow, cost] = mcmf.minCostMaxFlow(0, 3);
69    cout << flow << " " << cost << "\n"; // 3 9
70    return 0;
71}
72

This is a compact SPFA-based MCMF. It directly supports negative edge costs without potentials. It is easy to code and debug, suitable for small to medium inputs, but can be slow on worst-case graphs.

Time: O(F V E) in the worst case.Space: O(V + E).
Solving the Assignment Problem via Minimum Cost Maximum Flow
1#include <bits/stdc++.h>
2using namespace std;
3
4struct MinCostMaxFlow {
5    struct Edge { int to, rev; int cap; long long cost; };
6    int n; vector<vector<Edge>> g;
7    MinCostMaxFlow(int n): n(n), g(n) {}
8    void addEdge(int u, int v, int cap, long long cost){
9        Edge a{v, (int)g[v].size(), cap, cost};
10        Edge b{u, (int)g[u].size(), 0, -cost};
11        g[u].push_back(a); g[v].push_back(b);
12    }
13    pair<long long,long long> minCostMaxFlow(int s, int t, int req_flow){
14        const long long INF = (1LL<<60);
15        long long flow = 0, cost = 0;
16        vector<long long> pot(n,0), dist(n);
17        vector<int> pv(n), pe(n);
18        // No negative edges here; pot=0 is fine. If negative, run Bellman-Ford.
19        while (flow < req_flow) {
20            fill(dist.begin(), dist.end(), INF);
21            dist[s] = 0;
22            priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
23            pq.push({0,s});
24            while(!pq.empty()){
25                auto [du,u]=pq.top(); pq.pop(); if(du!=dist[u]) continue;
26                for(int i=0;i<(int)g[u].size();++i){ auto &e=g[u][i]; if(e.cap<=0) continue;
27                    long long nd=du + e.cost + pot[u] - pot[e.to];
28                    if(nd<dist[e.to]){ dist[e.to]=nd; pv[e.to]=u; pe[e.to]=i; pq.push({nd,e.to}); }
29                }
30            }
31            if(dist[t]==INF) break; // cannot send required flow
32            for(int v=0; v<n; ++v) if(dist[v]<INF) pot[v]+=dist[v];
33            int add = req_flow - (int)flow;
34            for(int v=t; v!=s; v=pv[v]) add=min(add, g[pv[v]][pe[v]].cap);
35            for(int v=t; v!=s; v=pv[v]){
36                auto &e=g[pv[v]][pe[v]]; auto &er=g[v][e.rev];
37                e.cap-=add; er.cap+=add; cost += 1LL*add*e.cost;
38            }
39            flow += add;
40        }
41        return {flow, cost};
42    }
43};
44
45int main(){
46    ios::sync_with_stdio(false);
47    cin.tie(nullptr);
48
49    // Assignment example: 3 workers, 3 jobs
50    // Cost matrix C[i][j]
51    vector<vector<int>> C = {
52        {4,1,3},
53        {2,0,5},
54        {3,2,2}
55    };
56    int n = (int)C.size();
57    int S = 2*n, T = 2*n+1;
58    MinCostMaxFlow mcmf(2*n+2);
59
60    // S -> workers
61    for(int i=0;i<n;++i) mcmf.addEdge(S, i, 1, 0);
62    // workers -> jobs with costs
63    for(int i=0;i<n;++i){
64        for(int j=0;j<n;++j){
65            mcmf.addEdge(i, n+j, 1, C[i][j]);
66        }
67    }
68    // jobs -> T
69    for(int j=0;j<n;++j) mcmf.addEdge(n+j, T, 1, 0);
70
71    auto [flow, cost] = mcmf.minCostMaxFlow(S, T, n);
72    cout << "Assigned pairs: " << flow << "\n";
73    cout << "Minimum total cost: " << cost << "\n"; // Expected 5
74
75    // Optional: recover which worker->job edges are used by checking reverse edges with cap>0
76    cout << "Assignments (worker -> job):\n";
77    for(int i=0;i<n;++i){
78        for(auto &e : mcmf.g[i]){
79            if(e.to>=n && e.to<2*n){ // edge to job node
80                int j = e.to - n;
81                // If reverse edge (job->worker) has positive cap, this i->j was used
82                const auto &rev = mcmf.g[e.to][e.rev];
83                if(rev.cap > 0) cout << i << " -> " << j << "\n";
84            }
85        }
86    }
87    return 0;
88}
89

We reduce the 3×3 assignment problem to MCMF with a bipartite graph: source to workers, workers to jobs (edge cost = assignment cost), jobs to sink. Each edge has capacity 1, and we send exactly n units of flow. The printed cost (5) matches the known optimum for the sample matrix.

Time: Building the network is O(n^2). Running MCMF is O(n * E log V) ≈ O(n^3 log n) here since F = n and E = O(n^2).Space: O(n^2) for the bipartite edges plus O(n) nodes and auxiliary arrays.