Find the Maximum Flow

Find the Maximum Flow

Given a graph with N vertices numbered 1 to N and M edges, the task is to find the max flow from vertex 1 to vertex N.

Ford-Fulkerson Algorithm for Maximum Flow Problem:)

Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints:

1.) Flow on an edge doesn’t exceed the given capacity of the edge.

2.) Incoming flow is equal to outgoing flow for every vertex except s and t.

Ford-Fulkerson Algorithm 
The following is simple idea of Ford-Fulkerson algorithm:
1) Start with initial flow as 0.
2) While there is a augmenting path from source to sink. 
           Add this path-flow to flow.
3) Return flow.

Time complexity of the above algorithm is O(max_flow * E). 
 If there is a path from source to sink in residual graph, then it is possible to add flow.
 Every edge of a residual graph has a value called residual capacity which is equal to
 original capacity of the edge minus current flow. 

Residual capacity is 0 if there is no edge between two vertices of residual graph.

To find an augmenting path, we can either do a BFS or DFS of the residual 
graph. We have used BFS in below implementation. 

Using BFS, we can find out if there is a path from source to sink. BFS also builds parent[] 
array. Using the parent[] array, we traverse through the found path and find possible flow 
through this path by finding minimum residual capacity along the path. We later add the 
found path flow to overall flow.

 we need to update residual capacities in the residual graph. We subtract path flow from all 
edges along the path and we add path flow along the reverse edges We need to add path flow along 
reverse edges because may later need to send flow in reverse direction 

#include <bits/stdc++.h>
using namespace std;
bool bfs(vector<vector<int> > adj,vector<int> &vis,vector<int> &parent,int n,int u)
{
    queue<int>  q;
    q.push(u);
    vis[u]=1;
    while(!q.empty())
    {
       int i=q.front();
       q.pop();
       for(int j=0;j<adj.size();++j)
       {
           if(vis[j]==0&&adj[i][j]>0)
           {
               q.push(j);
               vis[j]=1;
               parent[j]=i;
               if(j==n)
              return true;
           }
          
       }
    }
    return false;
}
int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        vector<vector<int> > adj(n,vector<int> (n,0));
        int u,v,w;
        for(int i=0;i<m;++i)
        {
            cin>>u>>v>>w;
            adj[u-1][v-1]+=w;
            adj[v-1][u-1]+=w;
        }
       
        int max_flow=0;
        while(true)
        {
            vector<int> vis(n,0),parent(n,-1);
            if(bfs(adj,vis,parent,n-1,0)==false)
             break;
           
            int v=n-1,mx=INT_MAX;
            while(parent[v]!=-1)
            {
                mx=min(adj[parent[v]][v],mx);
                v=parent[v];
            }
            v=n-1;
            while(parent[v]!=-1)
            {
                adj[parent[v]][v]-=mx;
                adj[v][parent[v]]+=mx;
                v=parent[v];
            }
           
            max_flow+=mx;
        }
        cout<<max_flow<<endl;
    }
    return 0;
}