Min-Cost Max-Flow
Send flow while optimizing total cost, which turns assignment and constrained transport models into graph problems.
Min-Cost Max-Flow
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Min-cost max-flow extends ordinary max flow by attaching a cost to each unit of flow on each edge. The goal is not just to push flow, but to push it as cheaply as possible. This is the right tool when a plain feasibility or cardinality answer is not enough.
When to Use It
Use min-cost max-flow when:
the network model is already natural,
each assignment or transfer has a linear cost,
you need either the cheapest way to send a fixed amount or the cheapest maximum flow.
Contest examples include weighted assignment, transportation, balancing supply and demand, and extracting \(k\) cheapest disjoint paths in small-to-medium graphs.
Core Idea
The standard contest implementation is successive shortest augmenting path:
keep a residual network with capacities and edge costs,
repeatedly find the cheapest augmenting path from \(s\) to \(t\),
push as much flow as possible on that path,
update residual capacities and accumulated cost.
Potentials reweight edges so Dijkstra can still be used even when the residual network contains negative-cost reverse edges.
Key Insight
The reverse edge is what makes cost corrections possible. If later decisions should undo some earlier expensive choice, the residual network exposes that option as a negative-cost reverse edge.
Operations / Main Technique
add forward and reverse residual edges,
shortest path in the residual network with reduced costs,
augment,
update vertex potentials.
Worked example.
In weighted bipartite assignment, each left-right compatibility edge carries a cost. Sending one unit of flow from source to left vertex to right vertex to sink corresponds exactly to choosing one assignment pair.
Correctness Intuition
Each augmentation chooses the cheapest possible additional residual path under the current reweighting. Potentials do not change which paths are optimal; they only keep reduced edge costs nonnegative so Dijkstra remains valid. When no more augmenting path exists, the flow is maximal, and the accumulated augmentations are minimum-cost among flows of that value.
Complexity Analysis
With Dijkstra and potentials, one augmentation is roughly \(O(E \log V)\). The total cost depends on how many times the algorithm augments, so the method is best when the graph and required flow are not enormous.
Implementation
The sample returns both:
the achieved flow,
the total minimum cost.
That makes it usable both for ``send exactly \(k\)'' and ``find the cheapest maximum flow'' style tasks.
Common Pitfalls
Forgetting to add the reverse edge with negated cost.
Not updating potentials after each shortest-path phase.
Using the algorithm on constraints where the number of augmentations is too large.
Confusing minimum-cost maximum flow with minimum-cost feasible flow of a specified amount.
Variants / Extensions
Min-cost flow for a fixed required amount.
Lower bounds and circulation reductions.
Potentials initialized by Bellman-Ford or SPFA if true negative edges exist initially.
Practice Problems
Weighted bipartite matching through a flow model.
Send \(k\) units through a graph with edge costs.
Transportation between supply and demand nodes.
References
Code
Contest-ready reference implementation for the idea explained above.
struct MinCostMaxFlow {
struct Edge {
int to;
int rev;
long long cap;
long long cost;
};
int n;
vector<vector<Edge>> graph;
explicit MinCostMaxFlow(int n) : n(n), graph(n) {}
void add_edge(int u, int v, long long cap, long long cost) {
Edge a{v, (int)graph[v].size(), cap, cost};
Edge b{u, (int)graph[u].size(), 0, -cost};
graph[u].push_back(a);
graph[v].push_back(b);
}
pair<long long, long long> min_cost_max_flow(int s, int t) {
const long long INF = (long long)4e18;
long long flow = 0;
long long cost = 0;
vector<long long> potential(n, 0), dist(n);
vector<int> parent_v(n), parent_e(n);
while (true) {
fill(dist.begin(), dist.end(), INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> 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)graph[v].size(); ++i) {
const Edge& e = graph[v][i];
if (e.cap == 0) continue;
long long nd = d + e.cost + potential[v] - potential[e.to];
if (nd < dist[e.to]) {
dist[e.to] = nd;
parent_v[e.to] = v;
parent_e[e.to] = i;
pq.push({nd, e.to});
}
}
}
if (dist[t] == INF) {
break;
}
for (int v = 0; v < n; ++v) {
if (dist[v] < INF) {
potential[v] += dist[v];
}
}
long long add = INF;
for (int v = t; v != s; v = parent_v[v]) {
const Edge& e = graph[parent_v[v]][parent_e[v]];
add = min(add, e.cap);
}
for (int v = t; v != s; v = parent_v[v]) {
Edge& e = graph[parent_v[v]][parent_e[v]];
e.cap -= add;
graph[v][e.rev].cap += add;
cost += add * e.cost;
}
flow += add;
}
return {flow, cost};
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.