library

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

View the Project on GitHub yuruhi/library

:heavy_check_mark: test/Dinic.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_A"
#include "./../Graph/Dinic.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	Dinic g(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		FLOW d;
		cin >> u >> v >> d;
		g.add_edge(u, v, d);
	}
	cout << g.solve(0, n - 1) << '\n';
}
#line 1 "test/Dinic.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_A"
#line 2 "Graph/FlowTemplate.cpp"
#include <vector>
#include <iostream>
#include <limits>

using FLOW = long long;
constexpr FLOW INF_FLOW = std::numeric_limits<FLOW>::max();
struct EdgeF {
	int to, rev;
	FLOW cap;
	EdgeF() : to(-1), rev(-1), cap(-1) {}
	EdgeF(int t, int r, FLOW c) : to(t), rev(r), cap(c) {}
	friend std::ostream& operator<<(std::ostream& os, const EdgeF& e) {
		return os << "->" << e.to << "(" << e.cap << ")";
	}
};
using GraphF = std::vector<std::vector<EdgeF>>;
#line 4 "Graph/Dinic.cpp"
#include <algorithm>
#include <queue>
#include <cassert>

class Dinic {
	int n;
	GraphF graph;
	std::vector<int> level, iter;
	void bfs(int s) {
		std::fill(level.begin(), level.end(), -1);
		level[s] = 0;
		std::queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto& e : graph[v]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}
	FLOW dfs(int v, int t, FLOW f) {
		if (v == t) return f;
		for (int i = iter[v]; i < graph[v].size(); ++i) {
			auto& e = graph[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				FLOW d = dfs(e.to, t, std::min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

public:
	Dinic(std::size_t _n) : n(_n), graph(n), level(n), iter(n) {}
	const GraphF& get_graph() {
		return graph;
	}
	void add_edge(int from, int to, FLOW cap) {
		assert(0 <= from && from < n);
		assert(0 <= to && to < n);
		graph[from].emplace_back(to, graph[to].size(), cap);
		graph[to].emplace_back(from, graph[from].size() - 1, 0);
	}
	FLOW solve(int s, int t) {
		FLOW result = 0;
		while (true) {
			bfs(s);
			if (level[t] < 0) return result;
			std::fill(iter.begin(), iter.end(), 0);
			FLOW f;
			while ((f = dfs(s, t, INF_FLOW)) > 0) result += f;
		}
	}
};
#line 4 "test/Dinic.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	Dinic g(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		FLOW d;
		cin >> u >> v >> d;
		g.add_edge(u, v, d);
	}
	cout << g.solve(0, n - 1) << '\n';
}
Back to top page