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<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

template<typename F,typename C>
struct MinCostFlow{
    struct Edge{
        int to;
        F cap;
        C cost;
        int rev;
    };
    const C INF;
    vector<vector<Edge>> v;
    vector<C> pot,dist;
    vector<int> prevv,preve;

    MinCostFlow(int n):v(n),INF(numeric_limits<C>::max()){}

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

    C min_cost_flow(int s,int t,F f){
        int n=v.size();
        C ret=0;
        using P = pair<C,int>;
        priority_queue<P,vector<P>,greater<P>> que;
        pot.assign(n, 0);
        prevv.assign(n, -1);
        preve.assign(n, -1);

        while(f>0){
            dist.assign(n, INF);
            que.emplace(0,s);
            dist[s]=0;
            while(!que.empty()){
                int cur=que.top().second;
                C d=que.top().first;
                que.pop();
                if(dist[cur]<d)continue;
                rep(i,v[cur].size()){
                    Edge &e = v[cur][i];
                    C next_cost = dist[cur]+e.cost+pot[cur]-pot[e.to];
                    if(e.cap>0 && dist[e.to]>next_cost){
                        dist[e.to]=next_cost;
                        prevv[e.to]=cur;
                        preve[e.to]=i;
                        que.emplace(dist[e.to],e.to);
                    }
                }
            }
            if(dist[t]==INF)return -1;
            rep(i,n)pot[i]+=dist[i];
            F add_flow = f;
            for(int u=t;u!=s;u=prevv[u]){
                add_flow=min(add_flow,v[prevv[u]][preve[u]].cap);
            }
            f-=add_flow;
            ret+=add_flow*pot[t];
            for(int u=t;u!=s;u=prevv[u]){
                Edge& e=v[prevv[u]][preve[u]];
                e.cap -=add_flow;
                v[e.to][e.rev].cap += add_flow;
            }
        }
        return ret;
    }
};

int main(){
    int n,m,f;
    cin>>n>>m>>f;
    MinCostFlow<int,int> mcf(n);
    rep(i,m){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        mcf.add_edge(a, b, c, d);
    } 
    cout<<mcf.min_cost_flow(0, n-1, f)<<endl;
    return 0;
}