Problem 5: Minimum Cost Flow
Problem Statement: Given a flow network with costs assigned to each edge, compute the minimum cost to send a desired amount of flow from source to sink.
Input
The first line contains n, m, and f (number of vertices, edges, and desired flow). Next m lines consist of u, v, capacity, and cost for each edge. Last line contains source and sink.
Output
Print the minimum cost to achieve the desired flow. If not possible, output -1.
Examples
Input:
4 5 150
0 1 100 1
0 2 100 2
1 2 1 0
1 3 100 3
2 3 100 1
0 3
Output:
350
Solution Explanation
Method 1: Use a variant of the Bellman-Ford algorithm or the SPFA algorithm to repeatedly find the shortest cost augmenting path while sending flow until the desired flow is reached. Method 2: Consider using capacity scaling along with Dijkstra’s algorithm modified for costs to improve efficiency on sparse graphs.
Solution in C++
#include
#include
#include
#include
#include
using namespace std;
struct Edge {
int v, capacity, cost, flow, rev;
};
const int INF = 1e9;
int main(){
int n, m, f;
cin >> n >> m >> f;
vector> adj(n);
auto addEdge = [&](int u, int v, int cap, int cost){
Edge a = {v, cap, cost, 0, (int)adj[v].size()};
Edge b = {u, 0, -cost, 0, (int)adj[u].size()};
adj[u].push_back(a);
adj[v].push_back(b);
};
for(int i=0; i> u >> v >> cap >> cost;
addEdge(u, v, cap, cost);
}
int s, t;
cin >> s >> t;
int flow = 0, cost = 0;
while(flow < f){
vector dist(n, INF), parent(n, -1), parentEdge(n, -1);
dist[s] = 0;
vector inQueue(n, false);
queue q;
q.push(s);
inQueue[s] = true;
while(!q.empty()){
int u = q.front(); q.pop();
inQueue[u] = false;
for(int i=0; i 0 && dist[e.v] > dist[u] + e.cost){
dist[e.v] = dist[u] + e.cost;
parent[e.v] = u;
parentEdge[e.v] = i;
if(!inQueue[e.v]){
q.push(e.v);
inQueue[e.v] = true;
}
}
}
}
if(dist[t] == INF) break;
int push_flow = f - flow;
for(int u = t; u != s; u = parent[u]){
push_flow = min(push_flow, adj[parent[u]][parentEdge[u]].capacity - adj[parent[u]][parentEdge[u]].flow);
}
for(int u = t; u != s; u = parent[u]){
Edge &e = adj[parent[u]][parentEdge[u]];
e.flow += push_flow;
adj[u][e.rev].flow -= push_flow;
}
flow += push_flow;
cost += push_flow * dist[t];
}
if(flow < f) cout << -1;
else cout << cost;
return 0;
}