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>

#define fread_siz 1024

inline int get_c(void)
{
	static char buf[fread_siz];
	static char *head = buf + fread_siz;
	static char *tail = buf + fread_siz;

	if (head == tail)
		fread(head = buf, 1, fread_siz, stdin);

	return *head++;
}

inline int get_i(void)
{
	register int ret = 0;
	register int neg = false;
	register int bit = get_c();

	for (; bit < 48; bit = get_c())
		if (bit == '-')neg ^= true;

	for (; bit > 47; bit = get_c())
		ret = ret * 10 + bit - 48;

	return neg ? -ret : ret;
}

template <class T>
inline T min(T a, T b)
{
	return a < b ? a : b;
}

const int inf = 2e9;
const int maxn = 2005;

int n, m;
int s, t;
int flow;

int edges;
int hd[maxn];
int nt[maxn];
int to[maxn];
int vl[maxn];
int fl[maxn];

inline void add(int u, int v, int f, int w)
{
	nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; vl[edges] = +w; hd[u] = edges++;
	nt[edges] = hd[v]; to[edges] = u; fl[edges] = 0; vl[edges] = -w; hd[v] = edges++;
}

int dis[maxn];
int pre[maxn];

inline bool spfa(void)
{
	static int que[maxn];
	static int inq[maxn];
	static int head, tail;
	
	memset(dis, 0x3f, sizeof(dis));
	head = 0, tail = 0;
	que[tail++] = s;
	pre[s] = -1;
	inq[s] = 1;
	dis[s] = 0;
	
	while (head != tail)
	{
		int u = que[head++], v; inq[u] = 0;
		
		for (int i = hd[u]; ~i; i = nt[i])
			if (dis[v = to[i]] > dis[u] + vl[i] && fl[i])
			{
				dis[v] = dis[u] + vl[i];
				pre[v] = i ^ 1;
				if (!inq[v])
					inq[v] = 1, que[tail++] = v;
			}
	}
	
	return dis[t] < 0x3f3f3f3f;
}

inline int expend(void)
{
	int newFlow = inf;
	
	for (int i = pre[t]; ~i; i = pre[to[i]])
		newFlow = min(newFlow, fl[i ^ 1]);
		
	for (int i = pre[t]; ~i; i = pre[to[i]])
		fl[i] += newFlow, fl[i^1] -= newFlow;
		
	return flow -= newFlow, newFlow * dis[t];
}

inline int mcmf(void)
{
	int ret = 0;
	
	while (spfa())
		ret += expend();
		
	return flow ? -1 : ret;
}

signed main(void)
{
	n = get_i();
	m = get_i();
	
	flow = get_i();
	
	memset(hd, -1, sizeof(hd));
	
	for (int i = 1; i <= m; ++i)
	{
		int u = get_i();
		int v = get_i();
		int f = get_i();
		int w = get_i();
		add(u, v, f, w);
	}
	
	s = n, t = n - 1;
	
	add(s, 0, flow, 0);
	
	printf("%d\n", mcmf());
}