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\n0 1 100 1\n0 2 100 2\n1 2 1 0\n1 3 100 3\n2 3 100 1\n0 3

Output:
350

Solution in C++


#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cstring>
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<vector<Edge>> 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<m; i++){
        int u, v, cap, cost;
        cin >> u >> v >> cap >> cost;
        addEdge(u, v, cap, cost);
    }
    int s, t;
    cin >> s >> t;
    int flow = 0, cost = 0;
    while(flow < f){
        vector<int> dist(n, INF), parent(n, -1), parentEdge(n, -1);
        dist[s] = 0;
        vector<bool> inQueue(n, false);
        queue<int> q;
        q.push(s);
        inQueue[s] = true;
        while(!q.empty()){
            int u = q.front(); q.pop();
            inQueue[u] = false;
            for(int i=0; i<adj[u].size(); i++){
                Edge &e = adj[u][i];
                if(e.capacity - e.flow > 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;
}