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;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

class minCostFlow {

	struct edge { int to, cap, cost, rev; };

	int V;
	vector<vector<edge>> G;
	vector<int> dist;
	vector<int> prevv;
	vector<int> preve;

public:

	minCostFlow(int n): G(n+10), dist(n+10), prevv(n+10), preve(n+10), V(n){
	}

	void addEdge(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});
	}

	int solve(int s, int t, int f) {
		int ret = 0;
		while(f > 0) {
			fill(dist.begin(), dist.end(), 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++) {
						edge &e = G[v][i];
						if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
							dist[e.to] = dist[v] + e.cost;
							prevv[e.to] = v;
							preve[e.to] = i;
							update = true;
						}
					}
				}
			}
			if(dist[t] == INF) {
				return -1;//流せない
			}

			int d = f;
			for(int v = t;v != s;v = prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			ret += d * dist[t];
			for(int v = t;v != s;v = prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return ret;
	}

};

int main(){

	int v,e,f;cin >> v >> e >> f;
	minCostFlow mcf(v);

	REP(i,e) {
		int a,b,c,d;cin >> a >> b >> c >> d;
		mcf.addEdge(a, b , c, d);
	}

	cout << mcf.solve(0, v-1, f) << endl;

	return 0;
}