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 <vector>
#include <queue>

#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;

typedef long long int ll;

// Primal-Dual Algorithm
// ref: https://tjkendev.github.io/procon-library/python/min_cost_flow/primal-dual.html
class MinCostFlow {
public:
	const ll INF = 1e18;
	const ll MAX_COST = 1e9+9;

	struct edge {
		int to;
		ll cap;
		ll cost;
		ll res;
		int r_edge;
	};

	int N;
	vector<vector<edge>> G;

	MinCostFlow(int n): N(n), G(n) {}

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

	ll flow(int S, int T, int flow){
		ll res = 0;
		vector<ll> H(N);  // ポテンシャル
		vector<int> pre_v(N), pre_e(N);

		while(flow > 0){
			vector<ll> D(N, INF);
			priority_queue<pair<ll,int>> que;

			D[S] = 0;
			que.emplace(0, S);
			while(!que.empty()){
				ll d = que.top().first;
				ll i = que.top().second;
				que.pop();
				if(D[i] < d) continue;
				rep(v, G[i].size()) if(G[i][v].res > 0) {
					edge &e = G[i][v];
					if (D[e.to] > D[i] + e.cost + H[i] - H[e.to]) {
						D[e.to] = D[i] + e.cost + H[i] - H[e.to];
						pre_v[e.to] = i;
						pre_e[e.to] = v;
						que.emplace(D[e.to], e.to);
					}
				}
			}

			if( D[T] == INF ) return -1;

			rep(i,N) H[i] += D[i];

			ll f = flow;
			for(int i=T; i != S; i = pre_v[i]) f = min(f, G[pre_v[i]][pre_e[i]].res);

			flow -= f;
			res += f * H[T];
			for(int i=T; i != S; i = pre_v[i]){
				edge &e = G[pre_v[i]][pre_e[i]];
				e.res -= f;
				G[i][e.r_edge].res += f;
			}
		}

		return res;
	}

	void reset(){
		for(auto &g: G) for(auto &e: g) e.res = e.cap;
	}
};


// verify: AOJ GRL_6_B
#include <iostream>
int main(){
	int V, E, F;
	cin >> V >> E >> F;
	MinCostFlow fl(V);
	rep(i,E){
		int	u, v, c, d;
		cin >> u >> v >> c >> d;
		fl.add_edge(u, v, c, d);
	}

	cout << fl.flow(0, V-1, F) << endl;
}