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:
/*
負の閉路が存在しない場合に使える
O(FElogV)

参考:
蟻本p202
https://ei1333.github.io/luzhiled/snippets/graph/primal-dual.html

verify:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B&lang=jp
*/

#include <bits/stdc++.h>
using namespace std;

template<typename flow_t,typename cost_t>
struct PrimalDual{
    struct edge{
        int to;
        flow_t cap;
        cost_t cost;
        int rev;
        bool isrev;
    };
    const cost_t inf;

    vector<vector<edge>> g;
    vector<cost_t> h,dist;
    vector<int> prevv,preve;

    PrimalDual(int N,cost_t inf_):g(N),inf(inf_){}

    void add_edge(int from,int to,flow_t cap,cost_t cost){
        g[from].emplace_back((edge){to,cap,cost,(int)g[to].size(),false});
        g[to].emplace_back((edge){from,0,-cost,(int)g[from].size()-1,true});
    }

    //fを流すのが不可能だったらinfを返す
    cost_t query(int s,int t,flow_t f){
        int N=g.size();
        cost_t ret=0;
        using pci=pair<cost_t,int>;
        priority_queue<pci,vector<pci>,greater<pci>> que;
        h.assign(N,0);
        preve.assign(N,-1);
        prevv.assign(N,-1);

        while(f>0){
            dist.assign(N,inf);
            que.emplace(0,s);
            dist[s]=0;
            while(!que.empty()){
                pci now=que.top(); que.pop();
                if(dist[now.second]<now.first) continue;
                for(int i=0;i<g[now.second].size();i++){
                    const edge &e=g[now.second][i];
                    cost_t nextCost=dist[now.second]+e.cost+h[now.second]-h[e.to];
                    if(e.cap>0 and dist[e.to]>nextCost){
                        dist[e.to]=nextCost;
                        prevv[e.to]=now.second; preve[e.to]=i;
                        que.emplace(nextCost,e.to);
                    }
                }
            }
        
            if(dist[t]==inf) return inf;
            for(int v=0;v<N;v++) h[v]+=dist[v];
            
            flow_t addflow=f;
            for(int v=t;v!=s;v=prevv[v]){
                addflow=min(addflow,g[prevv[v]][preve[v]].cap);
            }
            f-=addflow;
            ret+=addflow*h[t];
            for(int v=t;v!=s;v=prevv[v]){
                edge &e=g[prevv[v]][preve[v]];
                e.cap-=addflow;
                g[v][e.rev].cap+=addflow;
            }
        }
        return ret;
    }
};

int main(){
    int N,E,F;
    cin>>N>>E>>F;
    PrimalDual<int,int> flow(N,1<<30);
    for(int i=0;i<E;i++){
        int s,t,cap,cost;
        cin>>s>>t>>cap>>cost;
        flow.add_edge(s,t,cap,cost);
    }
    int x=flow.query(0,N-1,F);
    if(x==(1<<30)) x=-1;
    cout<<x<<"\n";
}