C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/フロー/最大流/Ford–Fulkerson 法 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A */ #include <iostream> #include "emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp" int main() { int v, e; std::cin >> v >> e; emthrm::FordFulkerson<long long> ford_fulkerson(v); while (e--) { int u_i, v_i, c_i; std::cin >> u_i >> v_i >> c_i; ford_fulkerson.add_edge(u_i, v_i, c_i); } std::cout << ford_fulkerson.maximum_flow(0, v - 1) << '\n'; return 0; }
#line 1 "test/graph/flow/maximum_flow/ford-fulkerson.test.cpp" /* * @title グラフ/フロー/最大流/Ford–Fulkerson 法 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A */ #include <iostream> #line 1 "include/emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp" #include <algorithm> #include <limits> #include <vector> namespace emthrm { template <typename T> struct FordFulkerson { struct Edge { int dst, rev; T cap; explicit Edge(const int dst, const T cap, const int rev) : dst(dst), rev(rev), cap(cap) {} }; std::vector<std::vector<Edge>> graph; explicit FordFulkerson(const int n) : graph(n), timestamp(0), is_used(n, -1) {} void add_edge(const int src, const int dst, const T cap) { graph[src].emplace_back(dst, cap, graph[dst].size()); graph[dst].emplace_back(src, 0, graph[src].size() - 1); } T maximum_flow(const int s, const int t, T limit = std::numeric_limits<T>::max()) { T res = 0; while (limit > 0) { const T tmp = dfs(s, t, limit); ++timestamp; if (tmp == 0) break; limit -= tmp; res += tmp; } return res; } private: int timestamp; std::vector<int> is_used; T dfs(const int ver, const int t, const T flow) { if (ver == t) return flow; is_used[ver] = timestamp; for (Edge& e : graph[ver]) { if (is_used[e.dst] < timestamp && e.cap > 0) { const T tmp = dfs(e.dst, t, std::min(flow, e.cap)); if (tmp > 0) { e.cap -= tmp; graph[e.dst][e.rev].cap += tmp; return tmp; } } } return 0; } }; } // namespace emthrm #line 10 "test/graph/flow/maximum_flow/ford-fulkerson.test.cpp" int main() { int v, e; std::cin >> v >> e; emthrm::FordFulkerson<long long> ford_fulkerson(v); while (e--) { int u_i, v_i, c_i; std::cin >> u_i >> v_i >> c_i; ford_fulkerson.add_edge(u_i, v_i, c_i); } std::cout << ford_fulkerson.maximum_flow(0, v - 1) << '\n'; return 0; }