sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A" #include <bits/stdc++.h> #include "../../flow/ford_fulkerson.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int V, E; cin >> V >> E; FordFulkerson<int> flow(V); for (int i = 0; i < E; i++) { int u, v, c; cin >> u >> v >> c; flow.add_edge(u, v, c); } cout << flow.max_flow(0, V - 1) << endl; }
#line 1 "test/aoj/GRL_6_A.ford_fulkerson.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A" #include <bits/stdc++.h> #line 7 "flow/ford_fulkerson.hpp" template <typename T> class FordFulkerson { public: FordFulkerson() = default; explicit FordFulkerson(int n) : G(n), used(n) {} void add_edge(int u, int v, T cap) { G[u].push_back({v, (int)G[v].size(), cap}); G[v].push_back({u, (int)G[u].size() - 1, 0}); } T max_flow(int s, int t) { T flow = 0; while (true) { std::fill(used.begin(), used.end(), false); T f = dfs(s, t, INF); if (f == 0) return flow; flow += f; } } std::set<int> min_cut(int s) { std::stack<int> st; std::set<int> visited; st.push(s); visited.insert(s); while (!st.empty()) { int v = st.top(); st.pop(); for (auto& e : G[v]) { if (e.cap > 0 && !visited.count(e.to)) { visited.insert(e.to); st.push(e.to); } } } return visited; } private: struct Edge { int to, rev; T cap; }; const T INF = std::numeric_limits<T>::max() / 2; 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; } }; #line 7 "test/aoj/GRL_6_A.ford_fulkerson.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int V, E; cin >> V >> E; FordFulkerson<int> flow(V); for (int i = 0; i < E; i++) { int u, v, c; cin >> u >> v >> c; flow.add_edge(u, v, c); } cout << flow.max_flow(0, V - 1) << endl; }