Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define II pair<int,int>
- VI parent;
- int res[MAXN][MAXN]; //adjMat for residual network
- VII adjList;
- // MaxFlow BFS
- // Edmonds-Karp Algo, BFS with adjList [ O(V.E/2 (V+E)) ~ O(V.E^2) ]
- int bfs(int src, int dest){
- fill(all(parent), -1);
- parent[src]=-2;
- queue<II> q; q.push({src, INF});
- while(!q.empty()){
- int u = q.front().F;
- int f = q.front().S;
- q.pop();
- for(auto v:adjList[u]){
- if(parent[v]==-1 && res[u][v]>0){
- parent[v]=u;
- int nf = min(f, res[u][v]);
- if(v==dest) return nf;
- q.push({v, nf});
- }
- }
- }
- return 0;
- }
- int MaxFlow(int src, int dest){
- int max_flow=0;
- int inc_flow;
- while(inc_flow=bfs(src, dest)){
- max_flow += inc_flow;
- for(int u=dest ; u!=src ; u=parent[u]){
- res[parent[u]][u] -= inc_flow;
- res[u][parent[u]] += inc_flow;
- }
- }
- return max_flow;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement