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<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int inf=0xfffffff;
struct edge{
  int to,cap,cost,rev;
};
int v;
vector<edge> G[105];
int dist[105],prevv[105],preve[105];
void add_edge(int from,int to,int cap,int cost){
  G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
  G[to].push_back((edge){from,0,-1*cost,(int)G[from].size()-1});
}
int min_cost_flow(int s,int t,int f){
  int res=0;
  while(f>0){
    for(int i=0;i<105;i++) dist[i]=inf;
    dist[0]=0;
    bool update=true;
    while(update){
      update=false;
      for(int i=0;i<v;i++){
        if(dist[i]>=inf) continue;
        for(int j=0;j<G[i].size();j++){
          edge &e=G[i][j];
          if(e.cap>0&&dist[e.to]>dist[i]+e.cost){
            dist[e.to]=dist[i]+e.cost;
            prevv[e.to]=i;
            preve[e.to]=j;
            update=true;
          }
        }
      }
    }
    if(dist[t]>=inf) return -1;
    int d=f;
    for(int i=t;i!=s;i=prevv[i]){
      d=min(d,G[prevv[i]][preve[i]].cap);
      //cout<<preve[i]<<" ";
    }
    //cout<<endl;
    f-=d;
    res+=dist[t]*d;
    //cout<<"d:"<<d<<" route:";
    for(int v=t;v!=s;v=prevv[v]){
      edge &e=G[prevv[v]][preve[v]];
      //cout<<prevv[v]<<" ";
      e.cap-=d;
      G[v][e.rev].cap+=d;
    }
    //cout<<endl;

  }
  return res;
}
int main(){
  int e,f;
  cin>>v>>e>>f;
  for(int i=0;i<e;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    add_edge(a,b,c,d);
  }
  cout<<min_cost_flow(0,v-1,f)<<endl;
}