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 <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

template<class T> struct MinCostFlow {
  struct Edge {
    int to, rev;
    T cap, cost;
    Edge () {}
    Edge (int _to, T _cap, T _cost, int _rev) :
      to(_to), cap(_cap), cost(_cost), rev(_rev) {}
  };
  const T INF = numeric_limits<T>::max() / 2;
  int N;
  vector< vector<Edge> > G;
  vector<T> h;
  vector<T> dist;
  vector<int> prevv, preve;
  MinCostFlow (int n) : N(n), G(n), h(n), dist(n), prevv(n), preve(n) {}

  void add_edge(int from, int to, T cap, T cost) {
    G[from].push_back(Edge(to,cap,cost,G[to].size()));
    G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
  }

  T get_min(int s, int t, T f) {
    T ret = 0;
    for (int i=0; i<N; i++) h[i] = 0;
    while (f > 0) {
      priority_queue< pair<T,int>, vector< pair<T,int> >, greater< pair<T,int> > > que;
      for (int i=0; i<N; i++) dist[i] = INF;
      dist[s] = 0;
      que.push(make_pair(0,s));
      while (que.size() != 0) {
        pair<int,int> p = que.top();
        que.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
          Edge &e = G[v][i];
          if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
            prevv[e.to] = v;
            preve[e.to] = i;
            que.push(make_pair(dist[e.to], e.to));
          }
        }
      }
      if (dist[t] == INF) {
        return -1;
      }
      for (int v=0; v<N; v++) h[v] += dist[v];
      int d = f;
      for (int v=t; v!=s; v=prevv[v]) {
        d = min(d,G[prevv[v]][preve[v]].cap);
      }
      f -= d;
      ret += 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 ret;
  }
};

int main() {

  int V,E,F;
  cin >> V >> E >> F;
  MinCostFlow<int> inst(110);

  REP(i,E) {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    inst.add_edge(a,b,c,d);
  }

  cout << inst.get_min(0,V-1,F) << endl;

  return 0;
}