AOJ GRL_6_A: Network Flow - Maximum Flow
Ford-Fulkerson版。ほぼ蟻本の写経。
#include <bits/stdc++.h> using namespace std; struct edge { int to, cap, rev; }; vector<vector<edge>> G(101); vector<bool> used(1001); void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size() - 1}); } int dfs(int v, int t, int f) { if (v == t) return f; used[v] = true; for (size_t i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; for (;;) { fill(used.begin(), used.end(), false); int f = dfs(s, t, numeric_limits<int>::max()); if (f == 0) return flow; flow += f; } } int main() { int V, E; cin >> V >> E; vector<int> c(E); for (int i = 0; i < E; ++i) { int from, to, cap; cin >> from >> to >> cap; add_edge(from, to, cap); } cout << max_flow(0, V - 1) << endl; }
Dinic版。これも蟻本の写経。
#include <bits/stdc++.h> using namespace std; struct edge { int to, cap, rev; }; const int MAX_V = 101; vector<vector<edge>> G(MAX_V); vector<int> level(MAX_V), iter(MAX_V); void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size() - 1}); } void bfs(int s) { fill(level.begin(), level.end(), -1); queue<int> que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (size_t i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } int dfs(int v, int t, int 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]) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; for (;;) { bfs(s); if (level[t] < 0) return flow; fill(iter.begin(), iter.end(), 0); int f; while ((f = dfs(s, t, numeric_limits<int>::max())) > 0) { flow += f; } } } int main() { int V, E; cin >> V >> E; vector<int> c(E); for (int i = 0; i < E; ++i) { int from, to, cap; cin >> from >> to >> cap; add_edge(from, to, cap); } cout << max_flow(0, V - 1) << endl; }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3307521#1