int N, Source, Dest; vector<vi> C; vi Use; void addEdge(int u, int v, int w) { C[u][v] += w; C[v][u] += w; } int augment(int u, int val) { if (u == Dest) return val; Use[u] = true; for (int v = 0; v < N; ++v) { if (Use[v]) continue; if (C[u][v] <= 0) continue; int r = augment(v, min(val, C[u][v])); if (r > 0) { C[u][v] -= r; C[v][u] +=r; return r; } } return 0; } int maxFlow() { int flow = 0; Use = vi(N, 0); while (true) { fill(all(Use), false); int f = augment(Source, 1 << 30); if (f == 0) break; flow += f; } return flow; }
SyntaxHighlighter
Thursday, 19 June 2014
Поиск максимального потока в неориентированном графе
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment