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;
}

Comments

Post a Comment

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

-
          Getting Started With MEAN App Development I Started Learning AngularJs one year Back. It is always a nice experience to start learning something new. I used Some of my AngularJs skills in my Programming Calculator App. ( https://nikhilnihal.github.io/programmingcalculator/index.html ) Few Days Back , I Started my hands on NodeJs and ExpressJs. I watched many Youtube Videos and Tutorials of  NodeJs and ExpreesJs. After that , I thought to do a Small Project Using all my skills of AngularJs , NodeJs ,ExpressJs.  I followed a Youtube Video ( https://www.youtube.com/watch?v=kHV7gOHvNdk ) and Made a Small Project Similiar to this one.After that I also Learnt that how to deploy my MEAN app on heroku website( heroku.com ). My app uses MongoDB for database. So , i also used mLab ( https://mlab.com /),which provided me MongoDB hosting service. There is a very useful blog which helped me to learn how to deploy my app on heroku. ( ht...
Read more

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

-
http://codeforces.com/contest/476/problem/B #include < bits / stdc ++. h > using namespace std ; string s1 , s2 ; int val = 0 , n ; int dp [ 15 ][ 15 ]; int solve ( int s , int l , int f ) { int & ret = dp [ s ][ l ]; if ( s == l ) { if ( f == val ) return 1 ; else return 0 ; } int ct = 0 ; ///number of ways in starting is 0 if ( s2 [ s ]== '+' ) ct += solve ( s + 1 , l , f + 1 ); if ( s2 [ s ]== '-' ) ct += solve ( s + 1 , l , f - 1 ); if ( s2 [ s ]== '?' ) ct += solve ( s + 1 , l , f + 1 )+ solve ( s + 1 , l , f - 1 ); return ret = ct ; /// In the last return this value } int main () { int i , j , k , l ; double ans ; cin >> s1 >> s2 ; n = s1 . size (); for ( i = 0 ; i < n ; i ++) { if ...
Read more

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.

-
http://codeforces.com/contest/476/problem/A #include < bits / stdc ++. h > using namespace std ; int dp [ 10001 ][ 5055 ]; int fun ( int cu , int n , int m , int st ) { if ( st % m == 0 && cu == n ) { // cout<<st<<endl; return st ; } if ( cu > n || st > n || st > 5050 ) return 999999 ; int & ret = dp [ cu ][ st ]; if ( ret ) return ret ; int k1 = fun ( cu + 1 , n , m , st + 1 ); int k2 = fun ( cu + 2 , n , m , st + 1 ); return ret = min ( k1 , k2 ); } int main () { int n , m , i , j , k , l ; cin >> n >> m ; //if(n>m*2) // cout<<-1<<endl; k = fun ( 0 , n , m , 0 ); if ( k == 999999 ) cout <<- 1 << endl ; else cout << k << endl ; return 0 ; }
Read more