820 - Internet Bandwidth

Kallol · Post by **Kallol** » Thu Aug 23, 2007 4:10 pm

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 · Post by **divad4686** » Fri Feb 20, 2009 10:06 pm

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 · Post by mf » Sat Feb 21, 2009 7:22 pm

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 · Post by **holmes** » Wed Oct 21, 2009 4:35 pm

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 · Post by **ahmadfarid** » Wed Nov 18, 2009 9:15 pm

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 · Post by **onzo** » Thu Oct 27, 2011 8:32 pm

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

Kaspars · Post by **Kaspars** » Mon Dec 23, 2013 4:27 pm

Could someone provide some corner-case tests? All of the ones I've run, work correctly.

vsha041 · Post by **vsha041** » Sun Mar 30, 2014 8:35 am

Remember that you need to print new line after every test case including the last one. For some of the problems on UVA, we don't need to print a blank line after last test case. Not printing the blank line after the last test case will result in Wrong Answer and not Presentation Error. Test cases for this problem are available here https://gist.github.com/andmej/2046238

vsha041 · Post by **vsha041** » Sun Mar 30, 2014 8:50 am

Here is a monster test case and the answer is verfied through this website - http://uvatoolkit.com/problemssolve.php

Input

Code: Select all

Output

Code: Select all

Network 1
The bandwidth is 17928.

damihp · Post by **damihp** » Tue May 13, 2014 5:52 pm

Can anybody tell me why im gettin Runtime Error?
The big test case of vsha041 works well on my code..

Thx

Code: Select all

acc, thx lbv.

lbv · Post by **lbv** » Tue May 13, 2014 8:10 pm

damihp wrote:Can anybody tell me why im gettin Runtime Error?

It seems like you need to clear your p map at the end of each test case, otherwise values from previous cases can end up causing an infinite recursion inside augmentPath.

Try for example:

Input

Code: Select all

Output

Code: Select all

Network 1
The bandwidth is 2218.

Network 2
The bandwidth is 4768.

Network 3
The bandwidth is 0.

damihp · Post by **damihp** » Wed May 14, 2014 2:51 am

lbv wrote:
damihp wrote:Can anybody tell me why im gettin Runtime Error?
It seems like you need to clear your p map at the end of each test case, otherwise values from previous cases can end up causing an infinite recursion inside augmentPath.

damn! of course i needed clear the map...
ACC now, thx bro!

groovy.kmilo · Post by **groovy.kmilo** » Wed Jul 23, 2014 9:50 pm

Hello.

I am trying to solve this problem with Edmonds-Karp algorithm Maximun flow but i don't know why i am getting WA.

Can anybody help me figure what's wrong

Thanks in advance.

Code is in Java language

Code: Select all

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;



public class internetBandwidth {


	static int m[][];

	public static void main(String[] args) throws Exception {

		BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
		BufferedWriter out = new BufferedWriter( new OutputStreamWriter(System.out));

		int nodos = Integer.parseInt(in.readLine());
		int cont = 1;
		while (nodos!=0) {

			StringTokenizer stk = new StringTokenizer(in.readLine());

			int inicio =  Integer.parseInt(stk.nextToken());
			int destino =  Integer.parseInt(stk.nextToken());
			inicio--;
			destino--;
			int aristas =  Integer.parseInt(stk.nextToken());
			m = new int[nodos][nodos];

			for (int i = 0; i < aristas; i++) {
				stk = new StringTokenizer(in.readLine());
				int a = Integer.parseInt(stk.nextToken());
				int b = Integer.parseInt(stk.nextToken());
				int w = Integer.parseInt(stk.nextToken());
				a--;
				b--;
				m[a][b]=w;
				m[b][a]=w;
			}

			out.write("Network "+cont+"\n");
			out.write("The bandwidth is "+maxFlow(m, inicio, destino)+".\n");

			if (cont==1) 
				out.write("\n");

			nodos = Integer.parseInt(in.readLine());
			if (nodos!=0 && cont!=1) 
				out.write("\n");

			cont++;
		}
		out.flush();
		out.close();
		in.close();
	}

	public static int maxFlow(int[][] cap, int s, int t) {
		for (int flow = 0;;) {
			int df = findPath(cap, new boolean[cap.length], s, t, Integer.MAX_VALUE);
			if (df == 0)
				return flow;
			flow += df;
		}
	}

	static int findPath(int[][] cap, boolean[] vis, int u, int t, int f) {
		if (u == t)
			return f;
		vis[u] = true;
		for (int v = 0; v < vis.length; v++)
			if (!vis[v] && cap[u][v] > 0) {
				int df = findPath(cap, vis, v, t, Math.min(f, cap[u][v]));
				if (df > 0) {
					cap[u][v] -= df;
					cap[v][u] += df;
					return df;
				}
			}
		return 0;
	}
}

lbv · Post by **lbv** » Wed Jul 23, 2014 11:59 pm

groovy.kmilo wrote:Hello.

I am trying to solve this problem with Edmonds-Karp algorithm Maximun flow but i don't know why i am getting WA.

Hi. Check your code in regards to the following information from the problem statement:

There might be more than one connection between a pair of nodes -- see the test cases from previous messages in this thread.

Print a blank line after each test case -- the last test case is not an exception to this.

OJ Board

820 - Internet Bandwidth

820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Run time Error Plz Help

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth

Re: 820 - Internet Bandwidth