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

#define MAX_V 200
#define INF 1000000

typedef tuple<int,int,int,int> Edge; // to,cap,cost,rev
int V;
typedef vector<Edge> Vertex;
vector<Vertex> G(MAX_V);
int dist[MAX_V];
int prev_v[MAX_V], prev_e[MAX_V];

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

int min_cost_flow(int s, int t, int f){
    int total_cost=0;
    while(f>0){
        fill(dist,dist+V,INF);
        dist[s]=0;
        bool update=true;
        while(update){
            update=false;
            for(int v=0;v<V;v++){
                if(dist[v]==INF) continue;
                for(int i=0;i<G[v].size();i++){
                    auto& e = G[v][i];
                    int to=get<0>(e), cap=get<1>(e), cost=get<2>(e);
                    if(cap>0&&dist[to]>dist[v]+cost){
                        dist[to]=dist[v]+cost;
                        prev_v[to]=v;
                        prev_e[to]=i;
                        update=true;
                    }
                }
            }
        }
        if(dist[t]==INF){
            return -1;
        }
        int d=f;
        for(int v=t;v!=s;v=prev_v[v]){
            d=min(d, get<1>(G[prev_v[v]][prev_e[v]]));
        }
        f-=d;
        total_cost+=d*dist[t];
        for(int v=t;v!=s;v=prev_v[v]){
            auto& e=G[prev_v[v]][prev_e[v]];
            get<1>(e)-=d;
            get<1>(G[v][get<3>(e)])+=d;
        }
    }
    return total_cost;
}

int main(){
    int E,F;
    cin>>V>>E>>F;
    for(int i=0;i<E;i++){
        int u,v,c,d;
        cin>>u>>v>>c>>d;
        add_edge(u,v,c,d);   
    }
    cout<<min_cost_flow(0,V-1,F)<<endl;
}