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:
// this program implements Dinitz's algorithm

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int N = 110;
const int M = 2010;
const int inf = 0x3fffffff;

struct Edge {
	int to, cap, cost, next;
} es[M];

int S, T;  // source, sink
int SIZE = 0; // number of edges
int h[N]; // pointer to edge list
int dist[N], queue[N], inq[N]; // for calculating shortest path
int prev[N];

// add forward and backtracked edge
void add(int u, int v, int cap, int cost) {
	int i = SIZE++;
	es[i].to = v;
	es[i].cap = cap;
	es[i].cost = cost;
	es[i].next = h[u];
	h[u] = i; 
	int j = SIZE++;
	es[j].to = u;
	es[j].cap = 0;
	es[j].cost = -cost;
	es[j].next = h[v];
	h[v] = j; 
}

// returns whether find a shortest path from S to T
bool sssp(int n) {
	int front = 0, back = 0;
	for (int i = 0; i < n; i++) {
		dist[i] = inf;
		inq[i] = 0;
	}
	queue[back++] = S;
	dist[S] = 0;
	while (front != back) {
		int x = queue[front++];
		if (front == N) front = 0;
		inq[x] = 0;
		for (int i = h[x]; i != -1; i = es[i].next)
			if (es[i].cap > 0) {
				int y = es[i].to;
				int new_d = dist[x] + es[i].cost;
				if (new_d < dist[y]) {
					dist[y] = new_d;
					prev[y] = x;
					if (!inq[y]) {
						queue[back++] = y;
						if (back == N) back = 0;
						inq[y] = 1;
					}
				}
			}
	}
	return (dist[T] < inf);
}

// returns the flow pushed from x to T
int dfs(int x, int flow) {
	if (x == T) return flow;
	int ret = 0;
	for (int i = h[x]; i != -1 && flow > 0; i = es[i].next) {
		int y = es[i].to;
		if (prev[y] != x) continue;
		int f = dfs(y, std::min(flow, es[i].cap));
		if (f != 0) {
			es[i].cap -= f;
			es[i^1].cap += f;
			ret += f;
			flow -= f;
		}
	}
	return ret;
}

void run() {
	int n, m, u, v, c, d, flow, cost = 0;
	scanf("%d%d%d", &n, &m, &flow);
	memset(h, -1, sizeof(h));
	S = 0, T = n - 1;
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d%d", &u, &v, &c, &d);
		add(u, v, c, d);
	}
	while (flow > 0 && sssp(n)) {
		int f = dfs(S, flow);
		cost += f * dist[T];
		flow -= f;
	}
	if (flow > 0)
		printf("-1\n");
	else
		printf("%d\n", cost);
}

int main() {
	run();
}