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<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long ll;

bool debug = false;
const int NIL = -1;
const int INF = 1000000000;
const int NUM = 100010;
clock_t START, END;

int V, E, F;

struct Edge {
	int from, to, cap, flow, cost;
	Edge(int u, int v, int c, int f, int w) :from(u), to(v), cap(c), flow(f), cost(w) {}
};

struct Graph {
	int n, m;
	vector<Edge> edges;
	vector<int> G[NUM];
	int inq[NUM];
	int d[NUM];
	int a[NUM];
	int p[NUM];

	void init(int n) {
		this->n = n;
		for (int i = 0; i < n; i++)
			G[i].clear();
		edges.clear();
	}

	void AddEdge(int from, int to, int cap, int cost) {
		edges.push_back(Edge(from, to, cap, 0, cost));
		edges.push_back(Edge(to, from, 0, 0, -cost));
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}

	bool BellmanFord(int s, int t, int& flow, ll& cost) {
		for (int i = 0; i < n; i++)
			d[i] = INF;
		memset(inq, 0, sizeof(inq));
		d[s] = 0;
		inq[s] = 1;
		p[s] = 0;
		a[s] = INF;

		queue<int> Q;
		Q.push(s);
		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			inq[u] = 0;
			for (int i = 0; i < G[u].size(); i++) {
				Edge& e = edges[G[u][i]];
				if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
					d[e.to] = d[u] + e.cost;
					p[e.to] = G[u][i];
					a[e.to] = min(a[u], e.cap - e.flow);
					if (!inq[e.to]) {
						Q.push(e.to);
						inq[e.to] = 1;
					}
				}
			}
		}
		if (d[t] == INF)
			return false;
		flow += a[t];
		if (a[t] <= F) {
			cost += (ll)d[t] * (ll)a[t];
			F -= a[t];
		}
		else {
			cost += (ll)d[t] * (ll)(F);
			F = 0;
		}
		for (int u = t; u != s; u = edges[p[u]].from) {
			edges[p[u]].flow += a[t];
			edges[p[u] ^ 1].flow -= a[t];
		}
		return true;
	}
	
	int MincostMaxflow(int s, int t, ll& cost) {
		int flow = 0;
		cost = 0;
		while (BellmanFord(s, t, flow, cost));
		return flow;
	}
};

Graph solve;

int main(void)
{
	if (debug) {
		START = clock();
		freopen("in29.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}
	ll COST;
	int u, v, c, d, f;
	cin >> V >> E >> F;
	f = F;
	solve.init(V);
	for (int i = 0; i < E; i++) {
		scanf("%d%d%d%d", &u, &v, &c, &d);
		solve.AddEdge(u, v, c, d);
	}
	if (solve.MincostMaxflow(0, V - 1, COST) >= f)
		cout << COST << endl;
	else
		cout << "-1" << endl;
	if (debug) {
		END = clock();
		double endtime = (double)(END - START) / 1000;
		printf("total time = %lf s", endtime);
	}
	return 0;
}