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>
static const int MAX=100;
static const int INFTY=(1<<30);
class edge{
public:
    int target, cap, cost, rev;
    edge(int target = 0, int cap =0, int cost = 0, int rev =0) : target(target), cap(cap), cost(cost), rev(rev) {}
};
int V;
std::vector<edge> G[MAX];
int h[MAX], dist[MAX], prevv[MAX], preve[MAX];

void add_edge(const int &source, const int &target, const int &cap, const int &cost) {
    G[source].push_back(edge(target, cap, cost, G[target].size()));
    G[target].push_back(edge(source, 0, -cost, G[source].size()-1));
}

int min_cost_flow(int s, int t, int f) {
    int res = 0;
    std::fill(h, h+V, 0);
    while(f > 0) {
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq;
        std::fill(dist, dist + V, INFTY);
        dist[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            std::pair<int, int> p = pq.top(); pq.pop();
            int current = p.second;
            if (dist[current] < p.first) continue;
            for (int i = 0; i < G[current].size(); i++) {
                edge &e = G[current][i];
                if (e.cap > 0 && dist[e.target] > dist[current] + e.cost + h[current] - h[e.target]) {
                    dist[e.target] = dist[current] + e.cost + h[current] - h[e.target];
                    prevv[e.target] = current; preve[e.target] = i;
                    pq.push({dist[e.target], e.target});
                }
            }
        }
        if (dist[t] == INFTY) return -1;
        for (int v = 0; v < V; v++) h[v] += dist[v];

        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = std::min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[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 E, f, source, target, cap, cost;
    std::scanf("%d %d %d", &V, &E, &f);
    for (int i = 0; i < E; i++) {
        std::scanf("%d %d %d %d", &source, &target, &cap, &cost);
        add_edge(source, target, cap, cost);
    }
    std::printf("%d\n", min_cost_flow(0, V-1, f));
    return 0;
}