UAIC Competitive Programming

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;
}