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 <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

using Weight=long long;
static const Weight INF=1LL<<57;

template <class T>
using gp_queue=priority_queue<T, deque<T>, less<T>>;

struct Arc {
    // accessible to the reverse edge
    size_t src, dst;
    Weight capacity, cost, flow;
    size_t rev;
    Arc() {}
    Arc(size_t src, size_t dst, Weight capacity, Weight cost=0):
        src(src), dst(dst), capacity(capacity), cost(cost), flow(0), rev(-1)
    {}
    Weight residue() const {
        return capacity - flow;
    }
};

bool operator<(const Arc &e, const Arc &f) {
    if (e.cost != f.cost) {
        return e.cost > f.cost;
    } else if (e.capacity != f.capacity) {
        return e.capacity > f.capacity;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Arcs=vector<Arc>;
using Node=vector<Arc>;
using FlowNetwork=vector<Node>;

void connect(FlowNetwork &g, size_t s, size_t d, Weight c=1, Weight k=0) {
    g[s].push_back(Arc(s, d, c, k));
    g[d].push_back(Arc(d, s, 0, -k));

    g[s].back().rev = g[d].size()-1;
    g[d].back().rev = g[s].size()-1;
}

void join(FlowNetwork &g, size_t s, size_t d, Weight c=1, Weight k=0) {
    g[s].push_back(Arc(s, d, c, k));
    g[d].push_back(Arc(d, s, c, k));

    g[s].back().rev = g[d].size()-1;
    g[d].back().rev = g[s].size()-1;
}

pair<Weight, Weight> mincost_flow(
    FlowNetwork &g, size_t s, size_t t, Weight F=INF
) {
    size_t V=g.size();
    vector<Arc *> prev(V, NULL);

    pair<Weight, Weight> total;  // <cost, flow>
    while (F > total.second) {
        vector<Weight> d(V, INF); d[s]=0;
        for (size_t i=0; i<V; ++i) {
            for (size_t v=0; v<V; ++v) {
                if (d[v] == INF) continue;
                for (Arc &e: g[v]) {
                    if (e.capacity <= 0) continue;

                    if (d[e.dst] > d[e.src] + e.cost) {
                        d[e.dst] = d[e.src] + e.cost;
                        prev[e.dst] = &e;
                    }
                }
            }
        }

        if (d[t] == INF) {
            total.first = -1;
            return total;
        }

        Weight f=F-total.second;
        for (Arc *e=prev[t]; e!=NULL; e=prev[e->src])
            f = min(f, e->capacity);

        total.second += f;
        total.first += f * d[t];
        for (Arc *e=prev[t]; e!=NULL; e=prev[e->src]) {
            e->capacity -= f;
            g[e->dst][e->rev].capacity += f;
        }
    }

    return total;
}

int main() {
    size_t V, E;
    Weight F;
    scanf("%zu %zu %lld", &V, &E, &F);

    FlowNetwork g(V);
    for (size_t i=0; i<E; ++i) {
        size_t u, v;
        Weight c, d;
        scanf("%zu %zu %lld %lld", &u, &v, &c, &d);

        connect(g, u, v, c, d);
    }

    printf("%lld\n", mincost_flow(g, 0, V-1, F).first);
    return 0;
}