820 - Internet Bandwidth

[Kallol]

well , I think its a straight-forward ford-fulkerson algo implementation . I considered bi-directional case and also the case of multiple edges between two nodes. Still I am getting WA. Here is my code. Any tricky input to produce wrong answer here ??

Code: Select all

removed after ACC

[divad4686]

Is there a way to find the test cases for this problem? i have a maxflow implementation in C# and would liek to test it with this problem

[mf]

No. Unless you rewrite your code into Java, C++ or Pascal, you wouldn't be able to test it here.

Take a look at data from DIMACS challenges - ftp://dimacs.rutgers.edu/pub/netflow/

[holmes]

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#define MAX 1000001
using namespace std;
string i2s(int n)
{  stringstream ss;
   ss<<n;
   return ss.str(); 
}
int s2i(string h)
{   stringstream ss;
    ss<<h;
    int n;
    ss>>n;
    return  n;
}
// 0 is the source node and n-1 is the sink node
int cap[120][120];
int fun[120][120];
int n;
bool flag;
vector<int> taken;
int improve=1000000000;
int parent[120];
int direction[120];
bool doit(int index)  // index means "a" and u want to see "b" from a such that improvement in inflow of "b" can be done
{  if(index==n-1)
   {  return true; // we are able to reach the sink
   }
   // case of a - > b
   for(int i=0;i<n;i++)
   {   if((cap[index][i]>0 && find(taken.begin(),taken.end(),i)==taken.end())&&(fun[index][i]<cap[index][i]))
       {   // means not already in the semipath and improvement can be done
           taken.push_back(i);
           improve=min(improve,cap[index][i]-fun[index][i]); // value for improvement has been done
           parent[i]=index;direction[i]=1; // case of the forward edge
           bool flag=doit(i);
           if(flag==true)
           {  return true; // we are able to reach the sink through this semipath
           }
           // else we are not able to reach by this path
       }
   }
   // case of b  < -  a
   for(int i=0;i<n;i++)
   {  if((cap[i][index]>0)&&(find(taken.begin(),taken.end(),i)==taken.end())&&(fun[i][index]>0)) // very imp
      {    taken.push_back(i);
           improve=min(improve,fun[i][index]); // value for improvement has been done
           parent[i]=index;direction[i]=-1;   // case of the reverse egde
           bool flag=doit(i);
           if(flag==true)
           {  return true; // we are able to reach the sink through this semipath
           }
           // else we are not able to reach by this path 
      }
   }
   // means we have not got any way to improve the required flow
   // need  to remove the index from the semipath taken
   taken.erase(taken.begin(),taken.begin()+taken.size()-1);
   parent[index]=-1;  // not in the path hence parent has been removed
   return false;
}
int main()
{  int p=1;
   while(scanf("%d",&n))
   {  if(n==0)
      {  break;
      }
      memset(cap,0,sizeof(cap)); // cap will be zero for the unconnencted nodes
      memset(direction,0,sizeof(direction));
      int s;int d;int c;scanf("%d %d %d",&s,&d,&c);s--;d--;
      for(int i=0;i<c;i++)
      {  int  x; int y; int val; scanf("%d %d %d",&x,&y,&val);x--;y--;
         if(x==s)     // these are the cases of changing the graph such that 0 is source ans n-1 is sink
         {   x=0;
         }
         else
         {  if(x==0)
            {  x=s;
            }
         }
         if(y==d)
         {  y=(n-1);
         }
         else
         {  if(y==(n-1))
            {  y=d;
            }
         }
         if(y==0)
         {  y=s;
         }
         else
         {  if(y==s)
            {  y=0;
            }
         }
         if(x==d)
         {   x=n-1;           
         }
         else
         {   if(x==n-1)
             {   x=d;
             }
         }
         cap[x][y]+=val;cap[y][x]+=val;
      }   
      // we need to improve the function matrix  initially least optimal
      memset(fun,0,sizeof(fun));memset(parent,-1,sizeof(parent));
      flag=true;
      while(flag) // while flag=true means we can do more improvement in the code
      { taken.clear();taken.push_back(0);
        flag=doit(0);   
        if(flag==true)
        {  // means improvement can be done
           int pos=n-1;vector<int> seen;seen.clear();seen.push_back(pos);
           while(pos!=-1)
           {  if(direction[pos]==1)
              {  fun[parent[pos]][pos]+=improve;
              }
              else
              {  fun[pos][parent[pos]]-=improve;
              }
              pos=parent[pos];
              if(find(seen.begin(),seen.end(),pos)!=seen.end())
              {  break;  // if this node is already visited
              }
              else
              {  seen.push_back(pos);
              }
           }
           // setting every thing for next iteration
           improve=1000000000;
           memset(parent,-1,sizeof(parent));
           memset(direction,0,sizeof(direction));
           taken.clear();
        }
        else
        {  break;
        }
      }
      int sum=0;
      for(int i=0;i<n;i++)
      {  sum+=fun[0][i];
      }
      printf("Network %d\n",p);
      printf("The bandwidth is %d.\n\n",sum);
      p++; 
   }   
   system("pause");
}


[ahmadfarid]

I keep getting wrong answer with my code. I don't know is it a problem in the algorithm or formatting?

Code: Select all

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

int n, e;
int g[1000][1000];
int capacity[1000][1000];
int flow[1000][1000];
int residual[1000][1000];

void ConstructResidual()
{
   // difference between capacity and flow + flow in other direction
   for(int i=0; i<n; i++)
      for(int j=0; j<n; j++)
      {
         //residual[i][j] = capacity[i][j] - flow[i][j] + flow[j][i];// in case of directed graph
         residual[i][j] = capacity[i][j] - flow[i][j]; // for undirected
      }
}



//Return the augmenting path
vector<int> BFSResidual(int s, int t)
{
   vector<int> path;
   // white = 0, gray = 1, black = 2.
   int color[1000];
   int d[1000];
   int pi[1000];
   for(int i=0; i<n; i++)
      if(i!=s)
      {
         color[i] = 0;
         d[i] = INT_MAX;
         pi[i] = -1; //-1 stands for nil
      }
      
   color[s] = 2;
   d[s] = 0;
   pi[s] = -1; //-1 = nil

   queue<int> q;
   
   q.push(s);

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

      for(int i=0; i<n; i++)
         if(residual[u][i]>0) // if there is an edge
            if(color[i] == 0)
            {
               color[i] = 1;
               d[i] = d[u] + 1;
               pi[i] = u;
               q.push(i);

               if(i==t)
               {
                  
                  path.push_back(i);
                  path.push_back(u);
            //      cout << i << " " << u << " ";
                  while(pi[u]!=-1)
                  {
            //         cout << pi[u] << " ";
                     u = pi[u];
                     path.push_back(u);
                  }
                  return path;
               }
            }
            
      color[u] = 2;

   }

   return path;
}
int main()
{
   int tests = 0;
   int s, t;
   
   
   while(true)
   {

      cin >> n >> s >> t >> e;
      
      if(n==0)
         break;

      // zero indexed of vertices
      s--;
      t--;

      int a, b, value;

      for(int i=0; i<n; i++)
         for(int j=0; j<n; j++)
         {
            g[i][j] = 0;
            flow[i][j] = 0;
            capacity[i][j] = 0;
         }

      for(int i=0; i<e; i++)
      {
         cin >> a >> b >> value;
         a--;
         b--;
         // zero indexed vertices
         g[a][b] = value; //only to run the normal BFS
         capacity[a][b] += value;
         capacity[b][a] += value; // only in case of undirected grpah
      }

   //   BFS(0,5);

      vector<int>path;

      ConstructResidual();
      // source and destination
      path = BFSResidual(0,n-1);
      
      // as long as there is an augmenting path
      while(path.size()>0)
      {
         // get the minimum of the flow to add
         int flowToAdd = INT_MAX;
         for(int i=1; i<path.size(); i++)
         {
            // path: carries the vertices on the graph of the residual network so we should get
            // the value of the minimum edge on the augmenting path on the residual network
            //MAKE SURE THE I,J ARE CORRECT
            int amount = residual[path[i]][path[i-1]];
            if(flowToAdd > amount)
               flowToAdd = amount;
         }

         // add the flow which was got from the augmenting path
         //MAKE SURE THE I,J ARE CORRECT
         for(int i=1; i<path.size(); i++)
         {
            //f[u,v] = f[u,v] + cf(p)
            flow[path[i]][path[i-1]] += flowToAdd;

            // to check: f[v,u] = -f[u,v]
            //flow[path[i-1]][path[i]] =   -flow[path[i]][path[i-1]] ;
            
            // this may work as well
            flow[path[i-1]][path[i]] -= flowToAdd;
         }

         ConstructResidual();
         // source and destination
         path = BFSResidual(0,n-1);
      }

      int maxFlow = 0;
      for(int i=0; i<n; i++)
         if(flow[0][i]>0)
            maxFlow += flow[0][i];

      cout << "Network " << ++tests << endl;
      cout << "The bandwidth is " << maxFlow << "." << endl << endl;
   }

   return 0;
}

[onzo]

i keep getting wrong answer i cant find out why!!!!!!! is there any tricky test case or anything wrong in my code its straight forward max flow i think

Code: Select all

#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <iomanip>
using namespace std;

int network[100][100];
vector<int> adj[100];
int source,dist,n;

 int find_path()
 {
    int from[100]= {-1} ;
    int vis[100] = {0} ;
    queue<int> q ;
    q.push(source);
    vis[source] = 1;
    from[source] = -1;
    while(!q.empty())
    {
       int head = q.front(); q.pop();
       vis[head] = 1;
       for(int i = 0 ; i < adj[head].size();i++)
       {
          if(network[head][adj[head][i]] > 0 && vis[adj[head][i]] == 0)
          {
             q.push(adj[head][i]);
             from[adj[head][i]] = head;
             if(adj[head][i] == dist)break;
          }
       }
    }

    int where = dist ,cap = 9999999 ;
    while(from[where] > -1)
    {
       int prev = from[where];
       cap = min(cap,network[prev][where]);
       where = prev;
    }
    where = dist;
    while(from[where] > -1)
    {
       int prev = from[where];
       network[prev][where] -= cap;
       network[where][prev] += cap;
       where = prev;
    }

    if (cap == 9999999)return 0;
  return cap;

 }

int max_flow()
{
   int res = 0;
   while(true)
   {
      int cap = find_path();
      if(cap == 0) break;
      res += cap;
   }
   return res;
}



int main()
{
   //freopen("1.in","r",stdin);
   for(int l=1;;l++)
   {
      cin>>n;
      if(n==0)break;
      memset(network,0,sizeof(network));
      int con;
      cin>>source>>dist>>con;
      source-=1;
      dist-=1;
      for(int i=0;i<n;i++)adj[i].clear();
      for(int i=0;i<con;i++){
         int a,b,band;
         cin>>a>>b>>band;
         network[a-1][b-1]+=band;
         network[b-1][a-1]+=band;
         adj[a-1].push_back(b-1);
         adj[b-1].push_back(a-1);
      }
      int res=max_flow();
      cout<<"Network "<<l<<endl<<"The bandwidth is "<<res<<"."<<endl;

   }
   return 0;
}