Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int res[MAX_V][MAX_V], mf, f, s, t;
- // global variables
- vi p;
- // p stores the BFS spanning tree from s, we use it to find path s -> t
- void augment(int v, int minEdge) {
- // traverse BFS spanning tree from s to t
- if (v == s) { f = minEdge; return; } // record minEdge in a global variable f
- else if (p[v] != -1) { augment(p[v], min(minEdge, res[p[v]][v])); // recursive
- res[p[v]][v] -= f; res[v][p[v]] += f; }
- // update
- }
- // inside int main()
- // set up the 2d AdjMat ‘res’, ‘s’, and ‘t’ with appropriate values
- mf = 0;
- // mf stands for max_flow
- while (1) {
- // O(VE^2) (actually O(V^3E) Edmonds Karp’s algorithm
- f = 0;
- // run BFS, compare with the original BFS shown in Section 4.2.2
- vi dist(MAX_V, INF); dist[s] = 0; queue<int> q; q.push(s);
- p.assign(MAX_V, -1);
- // record the BFS spanning tree, from s to t!
- while (!q.empty()) {
- int u = q.front(); q.pop();
- if (u == t) break;
- // immediately stop BFS if we already reach sink t
- for (int v = 0; v < MAX_V; v++)
- // note: this part is slow
- if (res[u][v] > 0 && dist[v] == INF)
- dist[v] = dist[u] + 1, q.push(v), p[v] = u;
- // three lines in one!
- }
- augment(t, INF); // find the minimum edge weight ‘f’ along this path, if any
- if (f == 0) break;
- // we cannot send any more flow (‘f’ = 0), terminate
- mf += f;
- // we can still send a flow, increase the max flow!
- }
- printf("%d\n", mf);
- // this is the max flow value
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement