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;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

const double EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = 2e5;
const double PI = acos(-1.0);

using namespace std;

struct MinCostFlow {
    struct edge {
        int to;
        int cap;
        int cost;
        int rev;
        bool is_rev;
    };
    const int INF;
    vector<vector<edge>> G;

    MinCostFlow(int n, int inf) : G(n), INF(inf) {
        ;
    }

    void add_edge(int from, int to, int cap, int cost) {
        G[from].push_back((edge){to, cap, cost, (int)G[to].size(), false});
        G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1, true});
    }

    int minCostFlow(int s, int t, int f) {
        const int N = G.size();
        int cost = 0;
        vector<int> prev_v(N, -1);
        vector<int> prev_e(N, -1);
        while (f > 0) {
            vector<int> dist(N, INF);
            dist[s] = 0;
            bool update = true;
            while (update) {
                update = false;
                for (int v=0; v<N; ++v) {
                    if (dist[v] == INF) continue;
                    for (int i=0; i<G[v].size(); ++i) {
                        edge &e = G[v][i];
                        if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                            dist[e.to] = dist[v] + e.cost;
                            prev_v[e.to] = v;
                            prev_e[e.to] = i;
                            update = true;
                        }
                    }
                }
            }
            if (dist[t] == INF) {
                return -1;
            }
            int d = f;
            for (int v=t; v!=s; v=prev_v[v]) {
                d = min(d, G[prev_v[v]][prev_e[v]].cap);
            }
            f -= d;
            cost += d * dist[t];
            for (int v=t;v!=s;v=prev_v[v]) {
                edge &e = G[prev_v[v]][prev_e[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return cost;
    }
};

int main() {
    int V, E, F;
    cin >> V >> E >> F;
    MinCostFlow mcf(V, INF);
    rep(i, E) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        mcf.add_edge(u, v, c, d);
    }
    cout << mcf.minCostFlow(0, V-1, F) << endl;
}