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 <iostream>
#include <vector>
#include <limits>

template <class Cap, class Cost, bool isDirect>
class MinCostFlow {
    struct Edge {
        int from, to;
        Cap cap;
        Cost cost;
        int rev;
        Edge(int from, int to, Cap cap, Cost cost, int rev)
            : from(from), to(to), cap(cap), cost(cost), rev(rev){};
    };

    class Graph {
    public:
        int size;
        std::vector<std::vector<Edge>> path;

        explicit Graph(int N = 0) : size(N), path(size) {}
        void span(int from, int to, Cap cap, Cost cost, int rev) {
            path[from].push_back(Edge(from, to, cap, cost, rev));
        }
        std::vector<Edge>& operator[](int v) { return path[v]; }
    };

public:
    const Cost INF = std::numeric_limits<Cost>::max();
    Graph graph;
    std::vector<Cost> dist;
    std::vector<Edge*> rev;

    explicit MinCostFlow(int N) : graph(N), dist(N), rev(N) {}

    void span(int from, int to, Cap cap, Cost cost) {
        graph.span(from, to, cap, cost, graph[to].size());
        graph.span(to, from, (isDirect ? 0 : cap), -cost, graph[from].size() - 1);
    }

    void BellmanFord(int s) {
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;

        bool update = true;
        while (update) {
            update = false;
            for (int v = 0; v < graph.size; ++v) {
                if (dist[v] == INF) continue;
                for (auto& e : graph[v]) {
                    if (e.cap > 0 && dist[e.to] > dist[e.from] + e.cost) {
                        dist[e.to] = dist[e.from] + e.cost;
                        rev[e.to] = &e;
                        update = true;
                    }
                }
            }
        }
    }

    Cost exec(int s, int g, Cap flow) {
        Cost ret = 0;

        while (flow > 0) {
            BellmanFord(s);
            if (dist[g] == INF) break;

            Cap f = flow;
            int v = g;
            while (v != s) {
                f = std::min(f, rev[v]->cap);
                v = rev[v]->from;
            }
            flow -= f;
            ret += f * dist[g];

            v = g;
            while (v != s) {
                // rev[v]->to = v
                rev[v]->cap -= f;
                graph[v][rev[v]->rev].cap += f;
                v = rev[v]->from;
            }
        }
        return (flow > 0 ? -1 : ret);
    }
};

int main() {
    int N, M, F;
    std::cin >> N >> M >> F;

    MinCostFlow<int, int, true> mcf(N);
    for (int i = 0; i < M; ++i) {
        int u, v, c, d;
        std::cin >> u >> v >> c >> d;
        mcf.span(u, v, c, d);
    }

    std::cout << mcf.exec(0, N - 1, F) << std::endl;
    return 0;
}