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 <bits/stdc++.h>
using namespace std;

using FLOW = int;
using COST = int;
const int MAX_V = 100;
const COST INF = 1000000000;

struct Edge {
    int rev, from, to;
    FLOW cap, icap;
    COST cost;
    Edge(int r, int f, int t, FLOW cp, COST cs)
        : rev(r), from(f), to(t), cap(cp), icap(cp), cost(cs) {}
};

struct Graph {
    int V;
    vector<Edge> list[MAX_V];
    Graph(int n = 0) { init(n); }
    void init(int n = 0) {
        V = n;
        for(auto &&v : list)
            v.clear();
    }
    void resize(int n = 0) { V = n; }
    void reset() {
        for(auto &&v : list)
            for(auto &&e : v)
                e.cap = e.icap;
    }
    inline vector<Edge> &operator[](int i) { return list[i]; }
    Edge &redge(Edge &e) { return list[e.to][e.rev + (e.from == e.to)]; }
    void addedge(int from, int to, FLOW cap, COST cost) {
        list[from].emplace_back(list[to].size(), from, to, cap, cost);
        list[to].emplace_back(list[from].size() - 1, to, from, 0, -cost);
    }
};

COST MinCostFlow(Graph &G, int s, int t, FLOW f) {
    COST dist[MAX_V];
    int prevv[MAX_V];
    int preve[MAX_V];
    COST res = 0;
    COST h[MAX_V];
    memset(h, 0, sizeof(h));
    using P = pair<COST, int>;
    priority_queue<P, vector<P>, greater<P>> que;
    while(f > 0) {
        fill(dist, dist + G.V, INF);
        dist[s] = 0;
        que.emplace(0, s);
        while(!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if(dist[v] < p.first) continue;
            for(int i = 0; i < (int)G[v].size(); i++) {
                Edge &e = G[v][i];
                if(e.cap > 0 &&
                   dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
        if(dist[t] == INF) return -1;
        for(int v = 0; v < G.V; v++)
            h[v] += dist[v];
        FLOW d = f;
        for(int v = t; v != s; v = prevv[v])
            d = min(d, G[prevv[v]][preve[v]].cap);
        f -= d;
        res += h[t] * d;
        for(int v = t; v != s; v = prevv[v]) {
            Edge &e = G[prevv[v]][preve[v]];
            Edge &re = G.redge(e);
            e.cap -= d;
            re.cap += d;
        }
    }
    return res;
}

int main() {
    int n, m;
    FLOW f;
    cin >> n >> m >> f;
    Graph G(n);
    for(int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        G.addedge(a, b, c, d);
    }
    cout << MinCostFlow(G, 0, n - 1, f) << "\n";

    return 0;
}