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 all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define pll     pair<long long, long long>
#define ll      long long

static const int INF = 0x3f3f3f3f;

struct edge {
        int to, cap, cost, rev;
};
int V;
vector<edge> g[101010];
int dist[101010];
int prevv[101010];
int preve[101010];
void add_edge(int from, int to, int cap, int cost) {
        g[from].push_back((edge) { to, cap, cost, (int)g[to].size() });
        g[to].push_back((edge) { from, 0, -cost, (int)g[from].size() - 1 });
}
int MinCostFlow(int s, int t, int f) {
        int res = 0;
        while (f > 0) {
                fill(dist, dist + V, INF);
                dist[s] = 0;
                bool update = true;
                while (update) {
                        update = false;
                        for (int v = 0; v < V; 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;
                                                prevv[e.to] = v;
                                                preve[e.to] = i;
                                                update = true;
                                        }
                                }
                        }
                }
                if (dist[t] == INF) return -1;
                int d = f;
                for (int v = t; v != s; v = prevv[v]) {
                        d = min(d, g[prevv[v]][preve[v]].cap);
                }
                f -= d;
                res += d * dist[t];
                for (int v = t; v != s; v = prevv[v]) {
                        edge &e = g[prevv[v]][preve[v]];
                        e.cap -= d;
                        g[v][e.rev].cap += d;
                }
        }
        return res;
}

int main() {
        int v, e, f;
        scanf("%d%d%d", &v, &e, &f);
        V = v;
        for (int i = 0; i < e; i ++) {
                int u, v, c, d;
                scanf("%d%d%d%d", &u, &v, &c, &d);
                add_edge(u, v, c, d);
        }
        printf("%d\n", MinCostFlow(0, V - 1, f));
        return 0;
}