test/flow/ford_fulkerson/aoj_grl_6_a.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 17:35:22+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A

Depends on

• Ford-Fulkerson (src/flow/ford_fulkerson.hpp)

Code

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

#include "src/flow/ford_fulkerson.hpp"

#include <iostream>

using namespace std;

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

	return 0;
}

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

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



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

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

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

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

	std::vector<std::vector<Edge>> g;
	std::vector<bool> used;

	T dfs(int v, int t, T f) {
		if (v == t) return f;
		used[v] = true;
		for (auto &e : g[v]) {
			if (!used[e.to] && e.cap > 0) {
				T d = dfs(e.to, t, std::min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					g[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

public:
	FordFulkerson(int n) : g(n), used(n) {}

	void add_edge(int from, int to, T cap, bool directed = true) {
		g[from].emplace_back(to, cap, g[to].size());
		g[to].emplace_back(from, (directed ? 0 : cap), g[from].size() - 1);
	}

	T max_flow(int s, int t) {
		T flow = 0;
		while (true) {
			used.assign(g.size(), 0);
			T f = dfs(s, t, INF);
			if (f == 0) break;
			flow += f;
		}
		return flow;
	}
};


#line 4 "test/flow/ford_fulkerson/aoj_grl_6_a.test.cpp"

#include <iostream>

using namespace std;

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

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	12 ms	7 MB
g++	01_small_00.in	AC	12 ms	7 MB
g++	01_small_01.in	AC	12 ms	7 MB
g++	01_small_02.in	AC	12 ms	7 MB
g++	01_small_03.in	AC	12 ms	7 MB
g++	02_corner_00.in	AC	12 ms	7 MB
g++	02_corner_01.in	AC	12 ms	7 MB
g++	02_corner_02.in	AC	12 ms	7 MB
g++	02_corner_03.in	AC	12 ms	7 MB
g++	03_random_00.in	AC	12 ms	7 MB
g++	03_random_01.in	AC	12 ms	7 MB
g++	03_random_02.in	AC	13 ms	7 MB
g++	03_random_03.in	AC	13 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	18 ms	7 MB
g++	03_random_07.in	AC	40 ms	7 MB
g++	04_rand_00.in	AC	12 ms	7 MB
g++	04_rand_01.in	AC	12 ms	7 MB
g++	04_rand_02.in	AC	12 ms	7 MB
g++	04_rand_03.in	AC	12 ms	7 MB
g++	04_rand_04.in	AC	12 ms	7 MB
g++	04_rand_05.in	AC	12 ms	7 MB
g++	04_rand_06.in	AC	12 ms	7 MB
g++	04_rand_07.in	AC	12 ms	7 MB
g++	05_large_00.in	AC	24 ms	7 MB
g++	05_large_01.in	AC	54 ms	7 MB
g++	05_large_02.in	AC	12 ms	7 MB
g++	05_large_03.in	AC	12 ms	7 MB
g++	05_large_04.in	AC	12 ms	7 MB
g++	05_large_05.in	AC	13 ms	7 MB
g++	06_biased_00.in	AC	12 ms	7 MB
g++	06_biased_01.in	AC	13 ms	7 MB
g++	06_biased_02.in	AC	13 ms	7 MB
g++	06_biased_03.in	AC	13 ms	7 MB
g++	06_biased_04.in	AC	14 ms	7 MB
g++	06_biased_05.in	AC	13 ms	7 MB
g++	06_biased_06.in	AC	162 ms	7 MB
g++	06_biased_07.in	AC	13 ms	7 MB
g++	06_biased_08.in	AC	12 ms	7 MB
clang++	00_sample_00.in	AC	11 ms	15 MB
clang++	01_small_00.in	AC	11 ms	15 MB
clang++	01_small_01.in	AC	11 ms	11 MB
clang++	01_small_02.in	AC	11 ms	9 MB
clang++	01_small_03.in	AC	11 ms	9 MB
clang++	02_corner_00.in	AC	10 ms	9 MB
clang++	02_corner_01.in	AC	11 ms	9 MB
clang++	02_corner_02.in	AC	10 ms	11 MB
clang++	02_corner_03.in	AC	11 ms	13 MB
clang++	03_random_00.in	AC	11 ms	13 MB
clang++	03_random_01.in	AC	11 ms	11 MB
clang++	03_random_02.in	AC	11 ms	11 MB
clang++	03_random_03.in	AC	11 ms	9 MB
clang++	03_random_04.in	AC	11 ms	13 MB
clang++	03_random_05.in	AC	11 ms	13 MB
clang++	03_random_06.in	AC	15 ms	14 MB
clang++	03_random_07.in	AC	32 ms	15 MB
clang++	04_rand_00.in	AC	12 ms	13 MB
clang++	04_rand_01.in	AC	11 ms	9 MB
clang++	04_rand_02.in	AC	11 ms	9 MB
clang++	04_rand_03.in	AC	11 ms	11 MB
clang++	04_rand_04.in	AC	11 ms	7 MB
clang++	04_rand_05.in	AC	12 ms	11 MB
clang++	04_rand_06.in	AC	12 ms	15 MB
clang++	04_rand_07.in	AC	12 ms	15 MB
clang++	05_large_00.in	AC	21 ms	8 MB
clang++	05_large_01.in	AC	42 ms	8 MB
clang++	05_large_02.in	AC	11 ms	9 MB
clang++	05_large_03.in	AC	11 ms	15 MB
clang++	05_large_04.in	AC	11 ms	11 MB
clang++	05_large_05.in	AC	11 ms	9 MB
clang++	06_biased_00.in	AC	11 ms	9 MB
clang++	06_biased_01.in	AC	11 ms	13 MB
clang++	06_biased_02.in	AC	12 ms	13 MB
clang++	06_biased_03.in	AC	12 ms	13 MB
clang++	06_biased_04.in	AC	12 ms	9 MB
clang++	06_biased_05.in	AC	12 ms	13 MB
clang++	06_biased_06.in	AC	120 ms	12 MB
clang++	06_biased_07.in	AC	11 ms	11 MB
clang++	06_biased_08.in	AC	11 ms	9 MB

Back to top page