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 INF 1e9
struct min_cost_flow
{
    struct edge{int to,cap,cost,rev;};
    int V;
    vector<vector<edge>> g;
public:
    min_cost_flow(int n)
    {
        V=n;
        g.resize(n,vector<edge>());
    }

    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, -cost,(int)g[from].size()-1});
    }
// s to t minmun flow 
// can't reach -1
    int run(int s,int t,int f)
    {
	    int res = 0;
	    int v = (int)g.size();
	    vector<int> prevv(v),preve(v);
	    while( f > 0 )
        {
		//bellmanford s-t周辺最短路を求める
		    vector<int> dist(v,INF);
		    dist[s] = 0;
		    bool update = true;
		    while(update)
            {
			    update = false;
			    for(int j= 0;j<v;j++)
                {
				    if(dist[j] == INF) continue;
				    for(int i= 0;i<g[j].size();i++)
                    {
					    edge &e = g[j][i];
					    if(e.cap > 0 && dist[e.to] > dist[j] + e.cost)
                        {
						    dist[e.to] = dist[j]  + e.cost;
						    prevv[e.to] = j;
						    preve[e.to] = i;
						    update = true;
					    }
				    }
			    }
		    }
		    if(dist[t] == INF ) return -1; //can't reach 
		    //s-t周辺に目いっぱい流す
		    int d = f;
		    for(int i = t; i!= s; i = prevv[i]) d = min(d,g[prevv[i]][preve[i]].cap);
		    f -= d;
		    res += d*dist[t];
		    for(int i = t; i!= s; i = prevv[i]){
		    	edge &e = g[prevv[i]][preve[i]];
		    	e.cap  -= d;
		    	g[i][e.rev].cap  += d;
		    }
	    }
	return res;
    }
};

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