tkmst201's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub tkmst201/Library

:heavy_check_mark: Test/Dinic.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A"

#include "GraphTheory/Dinic.hpp"

#include <cstdio>

int main() {
	int V, E;
	scanf("%d %d", &V, &E);
	Dinic<int> dinic(V);
	while (E--) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		dinic.add_edge(u, v, c);
	}
	printf("%d\n", dinic.max_flow(0, V - 1));
}
#line 1 "Test/Dinic.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A"

#line 1 "GraphTheory/Dinic.hpp"



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

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/Dinic.hpp
 */
template<typename T>
struct Dinic {
	using cap_type = T;
	
private:
	static constexpr cap_type EPS = std::is_floating_point<cap_type>() ? 1e-8 : 0;
	static constexpr cap_type INF = std::numeric_limits<cap_type>::max();
	struct Edge {
		int to, rev;
		cap_type c;
		Edge(int to, int rev, const cap_type & c) : to(to), rev(rev), c(c) {}
	};
	using Graph = std::vector<std::vector<Edge>>;
	Graph g;
	
public:
	Dinic(int n) : g(n) {}
	
	int size() const noexcept {
		return g.size();
	}
	
	void add_edge(int u, int v, const cap_type & cap) {
		assert(0 <= u && u < size());
		assert(0 <= v && v < size());
		assert(cap >= 0);
		g[u].emplace_back(v, g[v].size(), cap);
		g[v].emplace_back(u, g[u].size() - 1, 0);
	}
	
	cap_type max_flow(int s, int t) {
		assert(0 <= s && s < size());
		assert(0 <= t && t < size());
		assert(s != t);
		cap_type res = 0;
		std::vector<int> iter, level;
		while (true) {
			level.assign(size(), -1);
			std::queue<int> que;
			level[s] = 0;
			que.emplace(s);
			while (!que.empty() && level[t] == -1) {
				const int u = que.front();
				que.pop();
				for (const auto & e : g[u]) {
					if (e.c <= EPS || level[e.to] != -1) continue;
					level[e.to] = level[u] + 1;
					if (e.to == t) break;
					que.emplace(e.to);
				}
			}
			if (level[t] == -1) break;
			iter.assign(size(), 0);
			auto dfs = [&](auto self, int u, cap_type f) -> cap_type {
				if (u == t) return f;
				if (level[u] >= level[t]) return 0;
				for (int & i = iter[u]; i < static_cast<int>(g[u].size()); ++i) {
					auto & e = g[u][i];
					if (e.c <= EPS || level[u] >= level[e.to]) continue;
					const cap_type cur = self(self, e.to, std::min(f, e.c));
					if (cur > EPS) {
						e.c -= cur;
						g[e.to][e.rev].c += cur;
						return cur;
					}
				}
				return 0;
			};
			cap_type f;
			while ((f = dfs(dfs, s, INF)) > EPS) res += f;
		}
		return res;
	}
};


#line 4 "Test/Dinic.test.cpp"

#include <cstdio>

int main() {
	int V, E;
	scanf("%d %d", &V, &E);
	Dinic<int> dinic(V);
	while (E--) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		dinic.add_edge(u, v, c);
	}
	printf("%d\n", dinic.max_flow(0, V - 1));
}
Back to top page