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 rep(i,a,b) for(int i=a;i<b;i++)



#define ZERO(a) memset(a,0,sizeof(a))
template<int NV, class V> class MinCostFlow {
public:
	struct edge {
		int to, capacity; V cost; int reve;
		edge(int a, int b, V c, int d) {
			to = a; capacity = b; cost = c; reve = d;
		}
	};
	vector<edge> E[NV];
	int prev_v[NV], prev_e[NV]; V dist[NV];
	void add_edge(int x, int y, int cap, V cost) {
		E[x].push_back(edge(y, cap, cost, (int)E[y].size()));
		E[y].push_back(edge(x, 0, -cost, (int)E[x].size() - 1)); /* rev edge */
	}

	V mincost(int from, int to, int flow) {
		V res = 0; int i, v;
		ZERO(prev_v); ZERO(prev_e);
		while (flow>0) {
			fill(dist, dist + NV, numeric_limits<V>::max() / 2);
			dist[from] = 0;
			priority_queue<pair<int, int> > Q;
			Q.push(make_pair(0, from));
			while (Q.size()) {
				int d = -Q.top().first, cur = Q.top().second;
				Q.pop();
				if (dist[cur] != d) continue;
				if (d == numeric_limits<V>::max() / 2) break;
				rep(i, 0, E[cur].size()) {
					edge &e = E[cur][i];
					if (e.capacity>0 && dist[e.to]>d + e.cost) {
						dist[e.to] = d + e.cost;
						prev_v[e.to] = cur;
						prev_e[e.to] = i;
						Q.push(make_pair(-dist[e.to], e.to));
					}
				}
			}

			if (dist[to] == numeric_limits<V>::max() / 2) return -1;
			int lc = flow;
			for (v = to; v != from; v = prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for (v = to; v != from; v = prev_v[v]) {
				edge &e = E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};
//-----------------------------------------------------------------
typedef long long ll;
int NV, NE, F;
//-----------------------------------------------------------------
int main()
{
	MinCostFlow<100, ll> flow;

	cin >> NV >> NE >> F;

	rep(i, 0, NE) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		flow.add_edge(a, b, c, d);
	}

	cout << flow.mincost(0, NV - 1, F) << endl;
}