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 <cstdio>           // printf(), scanf()
#include <vector>
#include <algorithm>        // min(), fill()

using namespace std;
static const int MAX_V = 100;
static const int INF = 100000000;

typedef struct edge_tbl
{
	int to, cap, cost;
	unsigned long rev;
} edge;

vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];
int V;

int
min_cost_flow(int s, int t, int f)
{
	int res = 0;
	while (f > 0)
	{
		fill(dist, dist + V, INF);
		dist[s] = 0;
		bool update = true;
		while (update)
		{
			update = false;
			for (int v = 0; v < V; ++v)
			{
				if (dist[v] == INF)
					continue;

				for (unsigned 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;
		res += 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 res;
}

int
main(int argc, char** argv)
{
	int E, F;
	int u, v, cap, cost;

	scanf("%d %d %d", &V, &E, &F);
	for (int i = 0; i < E; ++i)
	{
		scanf("%d %d %d %d", &u, &v, &cap, &cost);
		G[u].push_back((edge){v, cap, cost, G[v].size()});
		G[v].push_back((edge){u, 0, -cost, G[u].size() - 1});
	}

	printf("%d\n", min_cost_flow(0, V - 1, F));
	return 0;
}