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 ll = long long;
using namespace std;
constexpr ll inf = 1e15;
constexpr ll mod = 1e9+7;

struct Edge {
    int to;
    int cap;
    int cost;
    int rev;
};
vector<Edge> edges[101];

int primalDual(int s, int t, int f) {
    int ret = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<int> potential(101, 0);
    vector<ll> dp(101, inf);
    vector<int> prevv(101, -1), preve(101, -1);
    // Dijkstra with potential
    while (f > 0) {
        dp.assign(101, inf);
        dp[s] = 0;
        q.push(make_pair(0, s));
        while (!q.empty()) {
            auto p = q.top();
            q.pop();
            if (dp[p.second] < p.first) continue;
            for (int i = 0; i < edges[p.second].size(); i++) {
                auto&& edge = edges[p.second][i];
                int nextCost = dp[p.second] + edge.cost + potential[p.second] - potential[edge.to];
                if (edge.cap > 0 && dp[edge.to] > nextCost) {
                    dp[edge.to] = nextCost;
                    prevv[edge.to] = p.second;
                    preve[edge.to] = i;
                    q.push(make_pair(nextCost, edge.to));
                }
            }
        }
        if (dp[t] == inf) return -1;
        for (int v = 0; v <= 100; v++) if (dp[v] < inf) potential[v] += dp[v];
        int addFlow = f;
        for (int v = t; v != s; v = prevv[v]) {
            addFlow = min(addFlow, edges[prevv[v]][preve[v]].cap);
        }
        f -= addFlow;
        ret += addFlow * potential[t];
        for (int v = t; v != s; v = prevv[v]) {
            Edge& e = edges[prevv[v]][preve[v]];
            e.cap -= addFlow;
            edges[v][e.rev].cap += addFlow;
        }
    }

    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int V, E, F;
    cin>>V>>E>>F;
    for (int e = 0; e < E; e++) {
        int U, V, C, D;
        cin>>U>>V>>C>>D;
        edges[U].push_back(Edge{V, C, D, (int)edges[V].size()});
        edges[V].push_back(Edge{U, 0, -D, (int)edges[U].size()-1});
    }

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