Advertisement
omar-alhelo

Edmonds-Karp (BFS) algo

Feb 20th, 2019
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1.  
  2. #define II pair<int,int>
  3. VI parent;
  4. int res[MAXN][MAXN]; //adjMat for residual network
  5. VII adjList;
  6. //                                         MaxFlow   BFS
  7. // Edmonds-Karp Algo,  BFS with adjList [ O(V.E/2   (V+E))  ~  O(V.E^2) ]
  8. int bfs(int src, int dest){
  9.   fill(all(parent), -1);
  10.   parent[src]=-2;
  11.   queue<II> q; q.push({src, INF});
  12.   while(!q.empty()){
  13.     int u = q.front().F;
  14.     int f = q.front().S;
  15.     q.pop();
  16.     for(auto v:adjList[u]){
  17.       if(parent[v]==-1 && res[u][v]>0){
  18.         parent[v]=u;
  19.         int nf = min(f, res[u][v]);
  20.         if(v==dest) return nf;
  21.         q.push({v, nf});
  22.       }
  23.     }
  24.   }
  25.   return 0;
  26. }
  27. int MaxFlow(int src, int dest){
  28.   int max_flow=0;
  29.   int inc_flow;
  30.   while(inc_flow=bfs(src, dest)){
  31.     max_flow += inc_flow;
  32.     for(int u=dest ; u!=src ; u=parent[u]){
  33.       res[parent[u]][u] -= inc_flow;
  34.       res[u][parent[u]] += inc_flow;
  35.     }
  36.   }
  37.   return max_flow;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement