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 <vector>
#include <queue>
#include <tuple>
int v, e;

struct Edge {
  Edge() {}
  Edge(int from, int to, int capacity, int cost, int rev) : from(from), to(to), capacity(capacity), cost(cost), rev(rev) {}
  int from, to;
  int capacity;
  int cost;
  int rev;
};

std::vector<Edge> edges[128];

void addEdge(int from, int to, int capacity, int cost) {
  int n1 = edges[from].size();
  int n2 = edges[to].size();
  edges[from].push_back(Edge(from, to, capacity, cost, n2));
  edges[to].push_back(Edge(to, from, 0, -cost, n1));
}                      

struct Result {
  Result() {}
  Result(int cost, int f) : cost(cost), f(f) {}
  int cost;
  int f;
};

int prev[128];
int prev_id[128];
int w[128];
int max_f[128];
void init_flow() {
  for(int i = 0; i < 128; ++i) {
    prev[i] = -1;
    prev_id[i] = -1;
    w[i] = (1 << 30);
    max_f[i] = 0;
  }
}

Result flow(int from, int to, int rem) {
  std::priority_queue< std::pair<int, int> > q;
  q.push(std::make_pair(0, from));
  w[from] = 0;
  max_f[from] = rem;
  while( not q.empty() ) {
    int n, weight;
    std::tie(weight, n) = q.top(); q.pop();
    // printf("(n) = (%d)\n", n);
    weight = -weight;
    for(int i = 0; i < (int)edges[n].size(); ++i) {
      Edge edge = edges[n][i];
      if( edge.capacity <= 0 ) continue;
      int nw = weight + edge.cost;
      if( w[edge.to] <= nw ) continue;
      w[edge.to] = nw;
      prev[edge.to] = n;
      prev_id[edge.to] = i;
      max_f[edge.to] = std::min(max_f[edge.from], edge.capacity);
      q.push(std::make_pair(-nw, edge.to));
    }
  }
  // for(int i = 0; i < v; ++i) {
  //   printf("node info[%d] : (w, max_f, prev, prev_id) = (%d, %d, %d, %d)\n", i, w[i], max_f[i], prev[i], prev_id[i]);
  // }
  int f = max_f[to];
  if( f == 0 ) return Result(0, 0);
  int m = to;
  int cost = 0;
  while( prev[m] != -1 ) {
    edges[prev[m]][prev_id[m]].capacity -= f;
    edges[m][edges[prev[m]][prev_id[m]].rev].capacity += f;
    cost += f * edges[prev[m]][prev_id[m]].cost;
    m = prev[m];
  }
  return Result(cost, f);
}

int minimum_cost_flow(int from, int to, int rem) {
  int cost = 0;
  for(;;) {
    init_flow();
    Result r = flow(from, to, rem);
    rem  -= r.f;
    cost += r.cost;
    if( rem == 0 ) return cost;
    if( r.f == 0 ) break;
    // printf("(rem, flow rate) = (%d, %d)\n", rem, r.f);
  }
  return -1;
}

int main() {
  int f;
  scanf("%d %d %d", &v, &e, &f);
  for(int i = 0; i < e; ++i) {
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    addEdge(a, b, c, d);
  }

  printf("%d\n", minimum_cost_flow(0, v - 1, f));
  
  return 0;
}