test/flow/primal_dual/aoj_grl_6_b.test.cpp

• View this file on GitHub
• Last update: 2023-12-12 23:23:17+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_B

Depends on

• Primal-Dual (src/flow/primal_dual.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_B

#include "src/flow/primal_dual.hpp"

#include <iostream>

using namespace std;

int main() {
	int v_sz, e_sz, flow;
	cin >> v_sz >> e_sz >> flow;
	PrimalDual<int, int> g(v_sz);
	for (int i = 0; i < e_sz; ++i) {
		int u, v, c, d;
		cin >> u >> v >> c >> d;
		g.add_edge(u, v, c, d);
	}
	cout << g.min_cost_flow(0, v_sz - 1, flow) << endl;

	return 0;
}

#line 1 "test/flow/primal_dual/aoj_grl_6_b.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_B

#line 1 "src/flow/primal_dual.hpp"



#include <limits>
#include <queue>
#include <algorithm>
#include <vector>

template<class T, class E>
class PrimalDual {
private:
	struct Edge {
		int to, rev;
		T cap;
		E cost;

		Edge(int to, T cap, E cost, int rev) : to(to), rev(rev), cap(cap), cost(cost) {}
	};

	static constexpr E INF = std::numeric_limits<E>::max();

	std::vector<std::vector<Edge>> g;
	std::vector<E> h, dist;
	std::vector<int> prevv, preve;

public:
	PrimalDual(int n) : g(n), h(n), dist(n), prevv(n), preve(n) {}

	void add_edge(int from, int to, T cap, E cost) {
		g[from].emplace_back(to, cap, cost, g[to].size());
		g[to].emplace_back(from, 0, -cost, g[from].size() - 1);
	}

	E min_cost_flow(int s, int t, T f) {
		E res = 0;
		std::priority_queue<std::pair<E, int>,
							std::vector<std::pair<E, int>>,
							std::greater<>>
			pq;

		while (f > 0) {
			dist.assign(g.size(), INF);
			pq.emplace(0, s);
			dist[s] = 0;
			while (!pq.empty()) {
				auto [now_dist, now_v] = pq.top();
				pq.pop();
				if (dist[now_v] < now_dist) continue;
				for (int i = 0; i < (int)g[now_v].size(); ++i) {
					Edge &e = g[now_v][i];
					E ncost = dist[now_v] + e.cost + h[now_v] - h[e.to];
					if (e.cap > 0 && dist[e.to] > ncost) {
						dist[e.to] = ncost;
						prevv[e.to] = now_v;
						preve[e.to] = i;
						pq.emplace(dist[e.to], e.to);
					}
				}
			}
			if (dist[t] == INF) return -1;
			for (int v = 0; v < (int)h.size(); ++v)
				if (dist[v] < INF) h[v] += dist[v];
			T d = f;
			for (int v = t; v != s; v = prevv[v])
				d = std::min(d, g[prevv[v]][preve[v]].cap);
			f -= d;
			res += d * h[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;
	}
};


#line 4 "test/flow/primal_dual/aoj_grl_6_b.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int v_sz, e_sz, flow;
	cin >> v_sz >> e_sz >> flow;
	PrimalDual<int, int> g(v_sz);
	for (int i = 0; i < e_sz; ++i) {
		int u, v, c, d;
		cin >> u >> v >> c >> d;
		g.add_edge(u, v, c, d);
	}
	cout << g.min_cost_flow(0, v_sz - 1, flow) << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	99 ms	7 MB
g++	01_small_00.in	AC	13 ms	7 MB
g++	01_small_01.in	AC	13 ms	7 MB
g++	01_small_02.in	AC	13 ms	7 MB
g++	01_small_03.in	AC	14 ms	7 MB
g++	02_corner_00.in	AC	14 ms	7 MB
g++	02_corner_01.in	AC	13 ms	7 MB
g++	02_corner_02.in	AC	14 ms	7 MB
g++	03_random_00.in	AC	13 ms	7 MB
g++	03_random_01.in	AC	13 ms	7 MB
g++	03_random_02.in	AC	14 ms	7 MB
g++	03_random_03.in	AC	14 ms	7 MB
g++	03_random_04.in	AC	14 ms	7 MB
g++	03_random_05.in	AC	14 ms	7 MB
g++	03_random_06.in	AC	15 ms	8 MB
g++	03_random_07.in	AC	14 ms	7 MB
g++	04_rand_00.in	AC	13 ms	7 MB
g++	04_rand_01.in	AC	13 ms	7 MB
g++	04_rand_02.in	AC	13 ms	7 MB
g++	04_rand_03.in	AC	13 ms	7 MB
g++	04_rand_04.in	AC	14 ms	7 MB
g++	04_rand_05.in	AC	14 ms	7 MB
g++	04_rand_06.in	AC	14 ms	7 MB
g++	04_rand_07.in	AC	14 ms	7 MB
g++	05_large_00.in	AC	15 ms	8 MB
g++	05_large_01.in	AC	16 ms	7 MB
g++	05_large_02.in	AC	15 ms	7 MB
g++	05_large_03.in	AC	15 ms	7 MB
g++	06_biased_00.in	AC	14 ms	7 MB
g++	06_biased_01.in	AC	15 ms	8 MB
g++	06_biased_02.in	AC	15 ms	7 MB
g++	06_biased_03.in	AC	17 ms	7 MB
clang++	00_sample_00.in	AC	12 ms	7 MB
clang++	01_small_00.in	AC	12 ms	11 MB
clang++	01_small_01.in	AC	12 ms	11 MB
clang++	01_small_02.in	AC	12 ms	13 MB
clang++	01_small_03.in	AC	12 ms	13 MB
clang++	02_corner_00.in	AC	12 ms	15 MB
clang++	02_corner_01.in	AC	11 ms	11 MB
clang++	02_corner_02.in	AC	12 ms	11 MB
clang++	03_random_00.in	AC	12 ms	7 MB
clang++	03_random_01.in	AC	12 ms	15 MB
clang++	03_random_02.in	AC	13 ms	15 MB
clang++	03_random_03.in	AC	13 ms	13 MB
clang++	03_random_04.in	AC	13 ms	11 MB
clang++	03_random_05.in	AC	14 ms	15 MB
clang++	03_random_06.in	AC	14 ms	13 MB
clang++	03_random_07.in	AC	13 ms	10 MB
clang++	04_rand_00.in	AC	12 ms	11 MB
clang++	04_rand_01.in	AC	12 ms	13 MB
clang++	04_rand_02.in	AC	12 ms	11 MB
clang++	04_rand_03.in	AC	13 ms	9 MB
clang++	04_rand_04.in	AC	13 ms	13 MB
clang++	04_rand_05.in	AC	13 ms	7 MB
clang++	04_rand_06.in	AC	13 ms	9 MB
clang++	04_rand_07.in	AC	13 ms	7 MB
clang++	05_large_00.in	AC	14 ms	12 MB
clang++	05_large_01.in	AC	14 ms	12 MB
clang++	05_large_02.in	AC	14 ms	14 MB
clang++	05_large_03.in	AC	15 ms	16 MB
clang++	06_biased_00.in	AC	14 ms	9 MB
clang++	06_biased_01.in	AC	14 ms	8 MB
clang++	06_biased_02.in	AC	13 ms	8 MB
clang++	06_biased_03.in	AC	15 ms	10 MB

Back to top page