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<bits/stdc++.h>

using namespace std;

#define mkp(x,y) (make_pair(x,y))
typedef pair<int,int> P;

class Edge
{
public:
    int to,cap,cost,rev;
    Edge(int a,int b,int c,int d)
    {
        to=a;cap=b;cost=c;rev=d;
    }
};

class MCMF
{
public:
    vector<vector<Edge> > G;
    vector<int> dist;
    vector<int> prev,pree;
    const int INF=2e9+10;
    MCMF(int n)
    {
        G.resize(n);
        dist.resize(n);
        prev.resize(n);
        pree.resize(n);
    }
    void add(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 mcmf(int s,int t,int f)
    {
        int res=0;
        while(f>0)
        {
            priority_queue<P,vector<P>,greater<P> > q;
            fill(dist.begin(),dist.end(),INF);
            dist[s]=0;
            q.push(P(0,s));
            while(!q.empty())
            {
                P p=q.top();q.pop();
                int v=p.second;
                if(dist[v]<p.first) continue;
                for(int i=0;i<G[v].size();i++)
                {
                    Edge &e=G[v][i];
                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost)
                    {
                        dist[e.to]=dist[v]+e.cost;
                        prev[e.to]=v;
                        pree[e.to]=i;
                        q.push(P(dist[e.to],e.to));
                    }
                }
            }
            if(dist[t]==INF)
            {
                return -1;
            }
            int tot=0;
            int d=f;
            for(int v=t;v!=s;v=prev[v])
            {
                Edge &e=G[prev[v]][pree[v]];
                d=min(d,e.cap);
                tot+=e.cost;
            }
            f-=d;
            for(int v=t;v!=s;v=prev[v])
            {
                Edge &e=G[prev[v]][pree[v]];
                e.cap-=d;
                G[v][e.rev].cap+=d;
            }
            res+=tot*d;
        }
        return res;
    }
};

int main()
{
    int V,E,F;
    while(cin>>V>>E>>F)
    {
        MCMF mcmf(V);
        for(int i=0;i<E;i++)
        {
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            mcmf.add(a,b,c,d);
        }
        cout<<mcmf.mcmf(0,V-1,F)<<endl;
    }
    return 0;
}