test/flow/dinic/aoj_grl_6_a.test.cpp

• View this file on GitHub
• Last update: 2024-01-06 12:34:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A

Depends on

• Dinic (src/flow/dinic.hpp)

Code

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

#include "src/flow/dinic.hpp"

#include <iostream>

using namespace std;

int main() {
	int v_sz, e_sz;
	cin >> v_sz >> e_sz;
	Dinic<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/dinic/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/dinic.hpp"



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

template<class T>
class Dinic {
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<int> level, iter;

	void bfs(int s) {
		level.assign(g.size(), -1);
		std::queue<int> q;
		level[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int const V = q.front();
			q.pop();
			for (auto &e : g[V]) {
				if (e.cap > 0 && level[e.to] == -1) {
					level[e.to] = level[V] + 1;
					q.push(e.to);
				}
			}
		}
	}

	T dfs(int v, int t, T f) {
		if (v == t) return f;
		for (int &i = iter[v]; i < (int)g[v].size(); ++i) {
			Edge &e = g[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				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:
	Dinic(int n) : g(n), level(n), iter(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) {
			bfs(s);
			if (level[t] == -1) break;
			iter.assign(g.size(), 0);
			while (true) {
				T f = dfs(s, t, INF);
				if (f == 0) break;
				flow += f;
			}
		}
		return flow;
	}
};


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

#include <iostream>

using namespace std;

int main() {
	int v_sz, e_sz;
	cin >> v_sz >> e_sz;
	Dinic<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	13 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	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	12 ms	7 MB
g++	03_random_03.in	AC	13 ms	7 MB
g++	03_random_04.in	AC	13 ms	8 MB
g++	03_random_05.in	AC	13 ms	7 MB
g++	03_random_06.in	AC	13 ms	7 MB
g++	03_random_07.in	AC	13 ms	8 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	13 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	13 ms	8 MB
g++	05_large_01.in	AC	13 ms	8 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	13 ms	7 MB
g++	06_biased_01.in	AC	13 ms	7 MB
g++	06_biased_02.in	AC	13 ms	8 MB
g++	06_biased_03.in	AC	13 ms	7 MB
g++	06_biased_04.in	AC	13 ms	8 MB
g++	06_biased_05.in	AC	13 ms	7 MB
g++	06_biased_06.in	AC	14 ms	7 MB
g++	06_biased_07.in	AC	13 ms	7 MB
g++	06_biased_08.in	AC	13 ms	7 MB
clang++	00_sample_00.in	AC	12 ms	15 MB
clang++	01_small_00.in	AC	11 ms	11 MB
clang++	01_small_01.in	AC	11 ms	9 MB
clang++	01_small_02.in	AC	12 ms	13 MB
clang++	01_small_03.in	AC	12 ms	11 MB
clang++	02_corner_00.in	AC	12 ms	13 MB
clang++	02_corner_01.in	AC	12 ms	15 MB
clang++	02_corner_02.in	AC	12 ms	13 MB
clang++	02_corner_03.in	AC	12 ms	13 MB
clang++	03_random_00.in	AC	12 ms	9 MB
clang++	03_random_01.in	AC	11 ms	7 MB
clang++	03_random_02.in	AC	12 ms	13 MB
clang++	03_random_03.in	AC	12 ms	9 MB
clang++	03_random_04.in	AC	12 ms	14 MB
clang++	03_random_05.in	AC	12 ms	10 MB
clang++	03_random_06.in	AC	13 ms	15 MB
clang++	03_random_07.in	AC	13 ms	13 MB
clang++	04_rand_00.in	AC	12 ms	7 MB
clang++	04_rand_01.in	AC	12 ms	13 MB
clang++	04_rand_02.in	AC	12 ms	15 MB
clang++	04_rand_03.in	AC	12 ms	7 MB
clang++	04_rand_04.in	AC	12 ms	11 MB
clang++	04_rand_05.in	AC	12 ms	11 MB
clang++	04_rand_06.in	AC	12 ms	9 MB
clang++	04_rand_07.in	AC	12 ms	13 MB
clang++	05_large_00.in	AC	13 ms	16 MB
clang++	05_large_01.in	AC	13 ms	11 MB
clang++	05_large_02.in	AC	11 ms	15 MB
clang++	05_large_03.in	AC	11 ms	7 MB
clang++	05_large_04.in	AC	12 ms	13 MB
clang++	05_large_05.in	AC	12 ms	13 MB
clang++	06_biased_00.in	AC	12 ms	9 MB
clang++	06_biased_01.in	AC	12 ms	13 MB
clang++	06_biased_02.in	AC	12 ms	11 MB
clang++	06_biased_03.in	AC	13 ms	11 MB
clang++	06_biased_04.in	AC	13 ms	13 MB
clang++	06_biased_05.in	AC	12 ms	11 MB
clang++	06_biased_06.in	AC	13 ms	12 MB
clang++	06_biased_07.in	AC	12 ms	7 MB
clang++	06_biased_08.in	AC	11 ms	7 MB

Back to top page