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>
#include <iomanip>
 
using namespace std;
 
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<char> VB;
 
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
 
const LD eps=1e-5;
//const long long INF=(LL)(1e9)*(LL)(1e9);
const int INF=1e9;
 
template<class T>
void chmin(T& a, const T& b)
{
	if(a>b)
		a=b;
}
template<class T>
void chmax(T& a, const T& b)
{
	if(a<b)
		a=b;
}
 
const LL pow(const LL p, const LL q)
{
	LL t=1;
	REP(i,q)
		t*=p;
	return t;
}

//print for container
/*
template<typename Iterator>
void print(const Iterator& first, const Iterator& last)
{
	auto&& back=prev(last);
	for(auto e=first; e!=last; e=next(e))
		cout<<*e<<" \n"[e==back];
}*/

template<typename Head>
void print(const Head& head)
{
	cout<<head<<endl;
}

template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
	cout<<head<<" ";
	print(tail...);
}

void io_speedup()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
}

template<typename T>
T read()
{
	T t;
	cin>>t;
	return t;
}


constexpr long long INF64 = 1e18;
 
using Weight=long long;

struct edge{
	int to,cap,cost,rev;
};

const int MAX_V=100;
int V;
vector<vector<edge>> G(MAX_V);
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

void add_edge(int from, int to, int cap, int cost)
{
	G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
	G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1});
}

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(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()
{
	REP(i,MAX_V)
		dist[i]=INF;
	int n,m,f;
    cin>>n>>m>>f;
	V=n;
    for(int i=0;i<m;++i){
        int u,v;
        Weight cap,cost;
        cin>>u>>v>>cap>>cost;
        add_edge(u,v,cap,cost);
    }
    cout<<min_cost_flow(0,n-1,f)<<endl;
}