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;
};

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

Result flow(int from, int to, int rem) {
  std::priority_queue< std::pair<int, int> > q;
  q.push(std::make_pair(0, from));
  nodes[from].w = 0;
  nodes[from].max_f = 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( nodes[edge.to].w <= nw ) continue;
      nodes[edge.to] = NodeInfo(nw, std::min(nodes[edge.from].max_f, edge.capacity), n, i);
      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 = nodes[to].max_f;
  if( f == 0 ) return Result(0, 0);
  int m = to;
  int cost = 0;
  while( nodes[m].prev != -1 ) {
    Edge& edge = edges[nodes[m].prev][nodes[m].prev_id];
    edge.capacity -= f;
    edges[m][edge.rev].capacity += f;
    cost += f * edge.cost;
    m = nodes[m].prev;
  }
  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;
}