NETWORK FLOW

 NETWORK   FLOW   ( E. Soldier and Traveling codeforces )

This concept of network flow is useful in problems like

 "Marriage problem"  in which the motive is to make maximum pairs.

In this problem we make a source and a sink. After that we find all the possible paths from source to sink (using bfs). while using bfs we have to save parents of each node in the path. It will help us to find the maximum flow in this path.

If we subtract this maxflow fom the path ,we will get residual graph. 



#include<bits/stdc++.h>

using namespace std;

int graph[1000][1000];

int main()
{
  int v,e,i,j,k,l,v1,v2;
  cin>>v>>e;

  for(i=1;i<=v;i++)           ///present situation   ('0' is source)
   cin>>graph[0][i];


  for(i=1;i<=v;i++)           ///future situation    ('2*v+1' is sink)
   cin>>graph[i+v][2*v+1];


   for(i=1;i<=e;i++)
   {
    cin>>v1>>v2;
    graph[v1][v2+v]=INT_MAX;
    graph[v2][v1+v]=INT_MAX;
   }

   for(i=1;i<=v;i++)
   graph[i][v+i]=1e6;

///-------------------------------------------flow started----------------------------------------------------///

while(1)
{
  queue<int> q;
  q.push(0);

 int parent[2*v+2];               ///parent array
  for(k=0;k<=2*v+1;k++)
    parent[k]=0;
     parent[0]=-1;                ///source ka parent -1



  int visited[2*v+2];             ///vsisited array
   for(k=0;k<=2*v+1;k++)
    visited[k]=0;
    visited[0]=1;               ///  only source is visited



  while(!q.empty())
  {
    int p=q.front();
    q.pop();

    visited[p]=1;

     for(k=0;k<=2*v+1;k++)
      if(graph[p][k]>0 && visited[k]==0)
      {
        parent[k]=p;
        q.push(k);
      }
  }
   //cout<<"hi";

   if(visited[2*v+1]==0)                         ///agar kisi v baar source se destination nahi aa paaye toh break;
     break;

      int mxflow=99999;
   for(k=2*v+1;parent[k]!=-1;)                  ///ye batayega ki maximum flow kitna ho sakta hai iss path mein
   {
    mxflow= min(mxflow,graph[parent[k]][k]);
    k=parent[k];
   }

    for(k=2*v+1;parent[k]!=-1;)
   {
    graph[k][parent[k]]+=mxflow;
    graph[parent[k]][k]-=mxflow;
    k=parent[k];
   }

}
for(i=1;i<=v;i++)
{
    if(graph[0][i]||graph[i+v][2*v+1])
    {
        cout<<"NO"<<endl;
        return 0;
    }
}
cout<<"YES"<<endl;

   for(i=1;i<=v;i++)
   {
      for(j=1;j<=v;j++)
      cout<<graph[j+v][i]<<" ";
      cout<<endl;
   }
return 0;
}