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 ll = long long;
#define rep(i, j) for(int i = 0; i < (int)(j); i++)
constexpr int INF = 1 << 28;
struct Edge {
    int to;
    ll capacity, cost, rev;
};
constexpr ll INFL = 1LL << 60;
struct Flow {
    int N;
    vector<vector<Edge>> E;
    Flow(int n) : N(n) {
        E.resize(N);
    }
    void add_arc(int from, int to, ll cap, ll cost = 0) {
        E[from].push_back(Edge{to, cap, cost, (ll)E[to].size()}); // E[to].size() ????????§??????????????????
        E[to].push_back(Edge{from, 0, -cost, (ll)E[from].size() - 1}); // ??????
    }
    // s -> t ??? f ??????????????????????°??????¨????¨?????????????????????? - 1
    // O(F|V||E|)
    // ????????¨??°??????????£???????
    ll min_cost_flow(int s, int t, ll f) {
        vector<int> prev_v(N), prev_e(N);
        
        auto bellmanford = [&] (int s) {
            vector<ll> dist(N, INFL);
            dist[s] = 0;
            bool updated = true;
            while(updated) {
                updated = false;
                rep(v, N) {
                    if(dist[v] >= INFL) continue;
                    rep(i, E[v].size()) {
                        auto &e = E[v][i];
                        if(e.capacity > 0 and dist[e.to] > dist[v] + e.cost) {
                            dist[e.to] = dist[v] + e.cost;
                            prev_v[e.to] = v;
                            prev_e[e.to] = i;
                            updated = true;
                        }
                    }
                }
            }            
            return dist;
        };
        
        ll res = 0;
        while(f > 0) {
            auto dist = bellmanford(s);
            if(dist[t] == INFL) return -1;
            ll d = f;
            // s -> t ???????°?????????????????????????????°??????? d ????±???????
            for(int v = t; v != s; v = prev_v[v]) {
                d = min(d, E[prev_v[v]][prev_e[v]].capacity);
            }
            // d ????????????            
            for(int v = t; v != s; v = prev_v[v]) {
                auto &e = E[prev_v[v]][prev_e[v]];
                e.capacity -= d;
                E[v][e.rev].capacity += d;
            }
            f -= d;
            res += d * dist[t]; // ??????????????¨
        }
        return res;
    }
};
int main() {
    int V, E, F; cin >> V >> E >> F;
    Flow f(V);
    rep(i, E) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        f.add_arc(u, v, c, d);                
    }
    cout << f.min_cost_flow(0, V - 1, F) << endl;
    return 0;
}