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 <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

const int INF = 1LL << 29;

struct edge {
    int to, cap, rev, cost;
    edge(int a, int b, int c, int d): to(a), cap(b), rev(c), cost(d) {}
};

int V, E, F;
vector<edge> graph[100];

int min_cost_flow(int s, int g, int f) {
    vector<int> min_dist(V, INF);
    vector<int> prev_v(V, -1), prev_e(V, -1);
    int ans = 0;
    while (f > 0) {
        fill(begin(min_dist), end(min_dist), INF);
        min_dist[s] = 0;

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

        if (min_dist[g] == INF) {
            return -1;
        }

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

        ans += ff * min_dist[g];
        for (int t = g; t != s; t = prev_v[t]) {
            edge& e = graph[prev_v[t]][prev_e[t]];
            e.cap -= ff;
            graph[t][e.rev].cap += ff;
        }

        f -= ff;
    }
    return ans;
}

int main() {
    cin >> V >> E >> F;
    for (int j = 0; j < E; ++j) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        graph[u].emplace_back(v, c, (int)graph[v].size(), d);
        graph[v].emplace_back(u, 0, (int)graph[u].size()-1, -d);
    }

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