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 <vector>
#include <queue>
#include <iostream>
using namespace std;

#define MAX_E 1001
int V, E, F, US[MAX_E], VS[MAX_E], CAP[MAX_E], COST[MAX_E];

class MinCostFlow {
public:
  const int INFTY = (1 << 21);
  struct Edge { int t, cap, cost, rev; };
  struct P {
    int d, id;
    bool operator < (const P &other) const {
      return d > other.d;
    }
  };

  MinCostFlow(int V):
    V(V), G(V, vector<Edge>(0)), dist(V, INFTY), prevv(V, -1), preve(V, -1), potential(V, 0) {}

  void addEdge(int s, int t, int cap, int cost) {
    G[s].push_back({ t, cap, cost, (int)G[t].size() });
    G[t].push_back({ s, 0, -cost, (int)G[s].size() - 1 });
  }

  int calc(int s, int t, int f) {
    int res = 0;

    while (f > 0) {
      dijkstra(s);
      if (dist.at(t) == INFTY) return -1;
      for (int v = 0; v < V; v++) potential.at(v) += dist.at(v);

      int d = f;
      for (int v = t; v != s; v = prevv.at(v)) {
        int cap = G.at(prevv.at(v)).at(preve.at(v)).cap;
        d = min(d, cap);
      }
      f -= d;
      res += d * potential.at(t);
      for (int v = t; v != s; v = prevv.at(v)) {
        Edge &edge = G.at(prevv.at(v)).at(preve.at(v));
        edge.cap -= d;
        G.at(v).at(edge.rev).cap += d;
      }
    }

    return res;
  }

private:
  int V;
  vector<vector<Edge> > G;
  vector<int> dist, prevv, preve, potential;

  void dijkstra(int s) {
    reset(s);
    priority_queue<P> PQ;
    vector<bool> done(V, false);
    PQ.push({ 0, s });

    while (PQ.size()) {
      P p = PQ.top(); PQ.pop();
      if (done.at(p.id)) continue;
      done.at(p.id) = true;
      if (dist.at(p.id) < p.d) continue;
      for (int e = 0; e<G.at(p.id).size(); e++) {
        Edge &edge = G.at(p.id).at(e);
        if (done.at(edge.t)) continue;
        if (edge.cap <= 0) continue;
        if (dist.at(edge.t) <= dist.at(p.id) + edge.cost + potential.at(p.id) - potential.at(edge.t)) continue;
        dist.at(edge.t) = dist.at(p.id) + edge.cost + potential.at(p.id) - potential.at(edge.t);
        prevv.at(edge.t) = p.id;
        preve.at(edge.t) = e;
        PQ.push({ dist.at(edge.t), edge.t });
      }
    }
  }

  void reset(int s) {
    fill(dist.begin(), dist.end(), INFTY);
    dist.at(s) = 0;
  }
};

void input() {
  cin >> V >> E >> F;
  for (int i=0; i<E; i++) {
    cin >> US[i] >> VS[i] >> CAP[i] >> COST[i];
  }
}

void solve() {
  MinCostFlow mcf(V);
  for (int i=0; i<E; i++) {
    mcf.addEdge(US[i], VS[i], CAP[i], COST[i]);
  }
  cout << mcf.calc(0, V-1, F) << endl;
}

int main() {
  input();
  solve();
}