Minimum-Cost Maximum Flow
Minimum-cost maximum flow first maximizes delivered quantity, then minimizes its cost among all flows of that value. Each directed edge has a capacity and a cost per transported unit. This models shipping, assignment with quotas and scheduling. Successive shortest augmenting paths repeatedly choose the cheapest legal residual adjustment. Because cancellation edges have negative costs, ordinary Dijkstra on original costs is invalid; potentials make the relevant reduced costs nonnegative.
Prerequisites: Network flow and residual edges; Dijkstra; Bellman–Ford. Difficulty: Advanced. Review: Dijkstra’s algorithm, Bellman–Ford & negative cycles, Dinic's Algorithm.
Build the idea
1. Attach costs to residual choices
An original edge with unit cost c has a reverse residual edge with cost −c: cancelling a unit refunds its earlier cost. Both partners carry separate residual capacities. A shortest residual path can include refunds, allowing the algorithm to repair an earlier expensive assignment. The objective is maximum FLOW before minimum COST, so we continue even when every remaining augmenting route has positive cost.
2. Initialize feasible potentials
Define reduced cost c′(u,v)=c(u,v)+p[u]−p[v]. If p are shortest distances from a virtual zero-cost source reaching all vertices, every positive residual arc has nonnegative reduced cost. The program obtains p by Bellman–Ford initialized to zero everywhere. Negative original edges are allowed, but an initial positive-capacity negative-cost cycle is outside this variant: a finite-capacity negative cycle may require profitable circulation, not necessarily imply unboundedness. The program detects it and prints an explicit unsupported message.
3. Run Dijkstra and update potentials
Dijkstra uses reduced costs and stores parent edge IDs. For every reachable vertex set p[v] += dist[v]. Triangle inequalities then ensure residual arcs reachable from s keep nonnegative reduced costs. Along a shortest path reduced costs become zero; newly enabled reverse partners also have zero reduced cost. Potential shifts telescope along any s→t path, so reduced and original path costs differ by the same endpoint constant: minimizing one minimizes the other. Unreachable potentials are left unchanged; new reverse arcs join reached vertices, so an unreachable region cannot suddenly become reachable.
4. Augment and maintain optimality
Send the bottleneck, change paired capacities, and add pushed×originalEdgeCost along the path. If the current fixed-value flow is minimum-cost and its residual graph has no negative cycle, a shortest augmenting path preserves that optimality for the larger value. Feasible reduced costs provide the no-negative-cycle invariant. When t is unreachable, flow is maximum; the invariant says its cost is minimum for that maximum value. We do not impose an arbitrary requested unit count.
5. Trace the sample
Two units can travel 1→2→4 at unit cost 1+1=2, and one unit travels 1→3→4 at unit cost 0+4=4. The first shortest path sends 2 units, then the other sends 1. Maximum flow is 3 and total cost is 2×2+1×4=8. If assignments conflict, reverse costs can change earlier routes, unlike independently selecting the cheapest original paths.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<limits>
#include<algorithm>
#include<utility>
using namespace std;
using ll=long long;
struct Edge{
int to;
ll cap,cost;
};
int main(){
int n,m,s,t;
if(!(cin>>n>>m>>s>>t)){
return 0;
}
vector<Edge>edges;
vector<vector<int>>graph(n+1);
for(int i=0;i<m;++i){
int u,v;
ll cap,cost;
cin>>u>>v>>cap>>cost;
int id=(int)edges.size();
edges.push_back({v,cap,cost});
edges.push_back({u,0,-cost});
graph[u].push_back(id);
graph[v].push_back(id^1);
}
const ll INF=numeric_limits<ll>::max()/4;
// Bellman-Ford from a virtual source with zero edges to EVERY vertex.
vector<ll>potential(n+1,0);
for(int pass=1;pass<=n;++pass){
bool changed=false;
for(int v=1;v<=n;++v){
for(int id:graph[v]){
const auto&e=edges[id];
if(e.cap>0&&potential[e.to]>potential[v]+e.cost){
potential[e.to]=potential[v]+e.cost;
changed=true;
}
}
}
if(!changed){
break;
}
if(pass==n){
cout<<"UNSUPPORTED NEGATIVE CYCLE\n";
return 0;
}
}
ll flow=0,totalCost=0;
for(;;){
vector<ll>dist(n+1,INF);
vector<int>parent(n+1,-1);
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,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 id:graph[v]){
const auto&e=edges[id];
if(e.cap==0){
continue;
}
ll reduced=e.cost+potential[v]-potential[e.to];
if(dist[e.to]>d+reduced){
dist[e.to]=d+reduced;
parent[e.to]=id;
pq.push({dist[e.to],e.to});
}
}
}
if(parent[t]==-1){
break;
}
for(int v=1;v<=n;++v){
if(dist[v]!=INF){
potential[v]+=dist[v];
}
}
ll pushed=INF;
for(int v=t;v!=s;v=edges[parent[v]^1].to){
pushed=min(pushed,edges[parent[v]].cap);
}
for(int v=t;v!=s;v=edges[parent[v]^1].to){
int id=parent[v];
totalCost+=pushed*edges[id].cost;
edges[id].cap-=pushed;
edges[id^1].cap+=pushed;
}
flow+=pushed;
}
cout<<flow<<' '<<totalCost<<'\n';
}
Complexity analysis
Bellman–Ford initialization costs O(VE). With A augmentations, the lazy-heap implementation costs O(A(V+E log(E+1))) afterwards; on a simple relevant graph this is often written O(A E log V). Each path adds at least one unit for integer capacities, so A≤F, a pseudo-polynomial dependence. O(V+E) memory. The stated limits n≤200, m≤2000, 0≤capacity≤10^6 and |cost|≤10^6 keep path and total costs within long long.
Example input and output
Read n m s t, then m lines u v capacity unitCost. 2≤n≤200, m≤2000, s≠t, valid labels, capacities≤10^6 and |cost|≤10^6. No initial positive-capacity negative-cost cycle is supported. Print maximumFlow minimumCost, or the stated unsupported-cycle message.
Input
4 4 1 4 1 2 2 1 2 4 2 1 1 3 1 0 3 4 1 4
Output
3 8
Two units cost 2 each and a third costs 4, giving maximum delivery 3 at cost 8.
Practical applications
Use when maximum throughput must also be cheapest, with capacities beyond one or sparse assignment constraints. For dense square perfect assignment, Hungarian is usually simpler and O(n³). For arbitrary initial negative-cost cycles, use a solver supporting cycle cancellation or a full min-cost circulation formulation. If costs are irrelevant, Dinic avoids shortest-cost overhead.
Check your understanding
Why does a reverse residual edge have negative unit cost?
Put it into practice
Test negative original edges in an acyclic network, then test a finite-capacity negative cycle.
Show a hint
The first case should optimize normally; the second should be explicitly rejected by this variant.