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 <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;


typedef int T; // cost type
typedef int U; // flow type

T INF = numeric_limits<T>::max(); // <limits>

struct edge {
    int to, rev;
    T cost;
    U cap;
    edge(int to, U cap, int rev, T cost) : to(to), rev(rev), cost(cost), cap(cap) {}
};

struct primal_dual {
    int N;
    vector<vector<edge> > graph;
    vector<int> prev_v, prev_e;
    vector<T> min_cost;

    primal_dual() {}
    primal_dual(int _N) { init(_N); }

    void init(int _N) {
        N = _N;
        graph.resize(N);
        prev_v.resize(N);
        prev_e.resize(N);
        min_cost.resize(N);
    }

    void add_edge(int u, int v, U cap, T cost) {
        graph[u].push_back(edge(v, cap, graph[v].size(), cost));
        graph[v].push_back(edge(u, 0, graph[u].size()-1, -cost));
    }

    T min_cost_flow(int s, int t, U F) {
        T val = 0;
        while (F > 0) {
            fill(min_cost.begin(), min_cost.end(), INF);
            min_cost[s] = 0;

            bool updated = true;
            while (updated) {
                updated = false;
                for (int v = 0; v < N; ++v) {
                    if (min_cost[v] == INF) continue;
                    for (int j = 0; j < graph[v].size(); ++j) {
                        edge& e = graph[v][j];
                        T cost = min_cost[v] + e.cost;
                        if (cost < min_cost[e.to] && e.cap > 0) {
                            updated = true;
                            min_cost[e.to] = cost;
                            prev_v[e.to] = v;
                            prev_e[e.to] = j;
                        }
                    }
                }
            }

            if (min_cost[t] == INF) {
                return (T)-1; // fail
            }

            U f = F;
            for (int v = t; v != s; v = prev_v[v]) {
                f = min(f, graph[prev_v[v]][prev_e[v]].cap);
            }

            F -= f;

            val += (T)f * min_cost[t];

            for (int v = t; v != s; v = prev_v[v]) {
                edge& e = graph[prev_v[v]][prev_e[v]];
                e.cap -= f;
                graph[v][e.rev].cap += f;
            }

        }
        return val;
    }
};

int V, E, F;
primal_dual pd;

int main() {
    cin >> V >> E >> F;
    pd.init(V);
    for (int j = 0; j < E; ++j) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        pd.add_edge(u, v, c, d);
    }

    cout << pd.min_cost_flow(0, V-1, F) << endl;
    return 0;
}