Problem: Examples

Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Output

6


Input




Output

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;

struct Edge {
    int from, to, cap, flow, cost;
    Edge(int from, int to, int cap, int flow, int cost):from(from), to(to), cap(cap), 
    flow(flow), cost(cost){}   
};

struct MaxflowMinCost {
    int n;
    vector<Edge> edges;
    vector<vector<int>> g;
    
    vector<int> p; //The id of the edge that connects to a vertex on the shortest path
    vector<int> a; //The possible flow change from the start to a vertex
    int flow = 0;
    int cost = 0;
    int f; //flow limit
    
    MaxflowMinCost(int n) : n(n) {
        g.assign(n + 1, vector<int>());
    }
    
    void addEdge(int from, int to, int cap, int cost) {
        edges.push_back(Edge(from , to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        g[from].push_back(edges.size() - 2);
        g[to].push_back(edges.size() - 1);   
    }
    
    int solve(int s, int t, int f) {
        this->f = f;
        while (bellmanFord(s, t)) {
        }
        return flow;
    }
    
    bool bellmanFord(int s, int t) {
        vector<int> d(n + 1, INF); //distance from s
        vector<bool> inq(n + 1, false);
        p.assign(n + 1, -1);
        a.assign(n + 1, 0);
           
        queue<int> q;
        p[s] = -2;
        a[s] = INF;
        d[s] = 0;
        inq[s] = true;
        
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int eid: g[u]) {
                Edge e = edges[eid];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = eid;
                    a[e.to] = min(a[u], e.cap - e.flow);
                    if (!inq[e.to]) { 
                        q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }
        if (d[t] == INF) {
            return false;
        }
        int aug = min(f, a[t]);
        f -= aug;
        
        flow += aug;
        cost += d[t] * aug;
     
        for (int u = t; u != s; u = edges[p[u]].from) {
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
        }
        
         if (f == 0) {
            return false;
        }
        
        return true;
    }   
};

int main() {
    int v, e, s, t, f;
    cin >> v >> e >> f;
    s = 0;
    t = v - 1;
    MaxflowMinCost maxflow(v);
    for (int i = 0; i < e; i++) {
        int from, to, cap, cost;
        cin >> from >> to >> cap >> cost;
        maxflow.addEdge(from, to, cap, cost);
    }
    int ans = maxflow.solve(s, t, f);
    if (ans < f) {
        cout << -1 << endl;
    }
    else {
        cout << maxflow.cost << endl;
    }
    return 0;
    
}