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>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair <int, int> pii;

const int INF = 0x3f3f3f3f;
int n, e, f, c[1005][1005];
vector <pii> adj[1005];

int dij(int s, int t, vector <int> &p, vector <int> &d) {
//	cout << "WTFF" << endl;
	fill(p.begin(), p.end(), -1);
	fill(d.begin(), d.end(), INF);
	vector <bool> inq(n + 5);
	p[s] = s, d[s] = 0, inq[s] = 1;
	queue <int> q;
	q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		inq[u] = 0;
//		cout << u << ' ' << d[u] << endl;
		for (pii i : adj[u]) {
			if (d[u] + i.se < d[i.fi] && c[u][i.fi] > 0) {
				d[i.fi] = d[u] + i.se;
				p[i.fi] = u;
//				cout << ">> " << i.fi << ' ' << i.se << endl;
				if (!inq[i.fi]) {
					q.push(i.fi);
					inq[i.fi] = 1;
				}
			}
		}
	}
//	for (int i = 0; i <= n; i++) cout << d[i] << ' ';
//	cout << endl;
	if (d[t] != INF) return d[t];
	else return -1;
}

int maxFlow(int s, int t) {
//	cout << "WTF" << endl;
	int rt = 0, cnt = 0, nf;
	vector <int> p, d;
	p.resize(n + 5);
	d.resize(n + 5);
	int t1;
	while (dij(s, t, p, d) != -1) {
		int bt = t;
		nf = INF;
		while (p[bt] != bt) {
			int v = p[bt];
			nf = min(nf, c[v][bt]);
//			cout << v << ' ' << bt << ' ' << d[v] << endl;
			bt = v;
		}
		nf = min(f - cnt, nf);
		rt += d[t] * nf, bt = t, cnt += nf;
//		cout << ">> " << rt << ' ' << d[t] << ' ' << nf << ' ' << cnt << endl;
		while (p[bt] != bt) {
			int v = p[bt];
			c[v][bt] -= nf;
			c[bt][v] += nf;
			bt = v;
		}
		if (cnt == f) break;
	}
	if (cnt == f) return rt;
	else return -1;
}

int main() {
	cin >> n >> e >> f;
	for (int i = 0; i < e; i++) {
		int u, v, cap, w;
		cin >> u >> v >> cap >> w;
		c[u][v] = cap;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, -w));
	}
	c[n - 1][n] = f;
	adj[n - 1].pb(mp(n, 0));
	adj[n].pb(mp(n - 1, 0));
	cout << maxFlow(0, n) << endl;
}