diff options
Diffstat (limited to 'maxFlow/edmondsKarp.cpp')
| -rw-r--r-- | maxFlow/edmondsKarp.cpp | 34 |
1 files changed, 0 insertions, 34 deletions
diff --git a/maxFlow/edmondsKarp.cpp b/maxFlow/edmondsKarp.cpp deleted file mode 100644 index ccfb1d2..0000000 --- a/maxFlow/edmondsKarp.cpp +++ /dev/null @@ -1,34 +0,0 @@ -int s, t, f; //source, target, single flow -int res[MAX_V][MAX_V]; //adj-matrix -vector< vector<int> > adjList; -int p[MAX_V]; //bfs spanning tree - -void augment(int v, int minEdge) { - if (v == s) { f = minEdge; return; } - else if (p[v] != -1) { - augment(p[v], min(minEdge, res[p[v]][v])); - res[p[v]][v] -= f; res[v][p[v]] += f; -}} - -nt maxFlow() { //first inititalize res, adjList, s and t - int mf = 0; - while (true) { - f = 0; - bitset<MAX_V> vis; vis[s] = true; - queue<int> q; q.push(s); - memset(p, -1, sizeof(p)); - while (!q.empty()) { //BFS - int u = q.front(); q.pop(); - if (u == t) break; - for (int j = 0; j < (int)adjList[u].size(); j++) { - int v = adjList[u][j]; - if (res[u][v] > 0 && !vis[v]) { - vis[v] = true; q.push(v); p[v] = u; - }}} - - augment(t, INF); //add found path to max flow - if (f == 0) break; - mf += f; - } - return maxFlow; -}
\ No newline at end of file |
