Network Flow - Maximum Flow
problem
Maximum Flow | Aizu Online Judge
code
#include <iostream> #include <vector> #define INF (1<<15) using namespace std; struct edge{ int to; int cap; int rev_id; }; class FordFulkerson { private: vector<vector<edge> > adj; int v; int e; vector<bool> visited; public: FordFulkerson() { cin >> v; cin >> e; adj.resize(v); for (int i = 0; i < e; ++i) { int u; int v; int c; cin >> u >> v >> c; adj[u].push_back((edge){v, c, adj[v].size()}); adj[v].push_back((edge){u, 0, adj[u].size() - 1}); } } int dfs(int from, int goal, int flow) { if(from == goal) return flow; visited[from] = true; for (int i = 0; i < adj[from].size(); ++i) { edge &e = adj[from][i]; if(!visited[e.to] && e.cap > 0) { int d = dfs(e.to, goal, min(e.cap, flow)); if(d > 0) { adj[from][i].cap -= d; adj[e.to][e.rev_id].cap += d; return d; } } } return 0; } void exec() { int flow_sum = 0; while(true) { visited = vector<bool>(v, false); int flow = dfs(0, v - 1, INF); if(flow == 0) { cout << flow_sum << endl; return; } flow_sum += flow; } } }; int main() { FordFulkerson ff = FordFulkerson(); ff.exec(); }