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;
int v, e;
vector<pair<int, int> > adj[110], revadj[110];
int capacity[1010], cost[1010], flowingthrough[1010], dis[110], pre[110], preedge[110], endofedge[1010];
void bellmanford()
{
	fill_n(dis, v, 1e9);
	dis[0] = 0;
	for (int f = 0; f < v; f++)
	{
		for (int i = 0; i < v; i++)
		{
			for (auto e : adj[i])
			{
				if (flowingthrough[e.second] != capacity[e.second])
				{
					if (dis[e.first] > dis[i] + cost[e.second])
					{
						dis[e.first] = dis[i] + cost[e.second];
						pre[e.first] = i;
						preedge[e.first] = e.second;
					}
				}
			}
			for (auto e : revadj[i])
			{
				if (flowingthrough[e.second])
				{
					if (dis[e.first] > dis[i] - cost[e.second])
					{
						dis[e.first] = dis[i] - cost[e.second];
						pre[e.first] = i;
						preedge[e.first] = e.second;
					}
				}
			}
		}
	}
}
pair<int, int> mincostmaxflow()
{
	int ans = 0;
	int totalcost = 0;
	while (1)
	{
		bellmanford();
		if (dis[v-1] == 1e9) break;
		ans++;
		// Augment path
		int a = v-1;
		while (a)
		{
		//	printf("%d ", a);
			int e = preedge[a];
			if (endofedge[e] == a) flowingthrough[e]++, totalcost += cost[e];
			else flowingthrough[e]--, totalcost -= cost[e];
			a = pre[a];
		}
		//printf("%d\n", a);
	}
	return { ans, totalcost };
}
int f;
int main()
{
	scanf("%d%d%d", &v, &e, &f);
	for (int i = 0; i < e; i++)
	{
		int a, b;
		scanf("%d%d%d%d", &a, &b, &capacity[i], &cost[i]);
		assert(a != b);
		endofedge[i] = b;
		adj[a].emplace_back(b, i);
		revadj[b].emplace_back(a, i);
	}
	adj[v-1].emplace_back(v, e);
	cost[e] = 0;
	endofedge[e] = v;
	capacity[e] = f;
	v++;
	auto ans = mincostmaxflow();
//	printf("%d %d\n", ans.first, ans.second);
	if (ans.first != f) printf("-1\n");
	else printf("%d\n", ans.second);
}