820 - Internet Bandwidth

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

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
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

divad4686
New poster
Posts: 1
Joined: Thu Apr 12, 2007 2:19 am

820 - Internet Bandwidth

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 820 - Internet Bandwidth

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
New poster
Posts: 1
Joined: Wed Oct 21, 2009 4:29 pm

Run time Error Plz Help

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
New poster
Posts: 6
Joined: Sun Apr 23, 2006 5:47 pm
Location: Cairo
Contact:

Re: 820 - Internet Bandwidth

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
New poster
Posts: 1
Joined: Thu Oct 27, 2011 8:27 pm

Re: 820 - Internet Bandwidth

Post by onzo » Thu Oct 27, 2011 8:32 pm

i keep getting wrong answer i cant find out why!!!!!!! :cry: :cry: 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
New poster
Posts: 1
Joined: Mon Dec 23, 2013 4:23 pm

Re: 820 - Internet Bandwidth

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
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 820 - Internet Bandwidth

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
Last edited by vsha041 on Sun Mar 30, 2014 12:00 pm, edited 1 time in total.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 820 - Internet Bandwidth

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

50
1 50 977
37 4 310
10 42 432
38 43 27
17 20 14
13 40 319
48 11 513
20 34 365
8 26 792
27 9 118
43 5 726
3 22 863
29 50 751
8 43 853
39 5 700
50 24 664
38 46 799
44 32 363
26 19 946
11 18 247
14 5 937
47 23 365
32 15 448
43 18 912
45 46 149
3 1 805
27 39 7
32 34 579
2 18 436
27 29 354
31 32 700
35 9 981
12 8 514
11 7 3
41 1 954
34 7 435
21 22 94
50 13 154
42 49 592
9 47 444
8 28 207
35 22 762
21 42 393
11 27 867
23 35 712
37 42 947
22 36 613
42 45 367
49 26 554
41 30 276
22 21 48
23 2 758
27 17 909
6 23 56
6 18 689
38 33 501
4 23 812
47 50 901
46 23 863
32 22 979
16 24 398
21 46 999
25 45 297
30 42 436
33 44 120
25 11 918
26 35 772
41 45 26
45 44 174
27 28 987
32 23 936
43 37 2
4 42 685
6 32 549
28 16 672
38 39 604
17 22 324
21 2 490
14 48 123
47 49 995
6 31 673
27 14 137
39 27 224
7 23 579
26 44 697
49 47 132
35 47 254
27 6 230
20 10 233
25 22 71
34 1 592
27 47 404
14 42 441
1 16 602
30 17 459
18 30 749
42 24 600
39 22 313
43 10 679
31 5 629
30 50 86
49 42 988
31 6 481
10 13 105
17 20 662
35 46 587
9 16 806
4 39 433
29 20 952
4 22 930
31 27 201
6 40 119
24 39 920
7 31 904
26 23 569
28 49 701
50 41 23
7 14 673
33 45 817
3 29 974
16 2 572
35 34 418
37 44 975
16 47 412
49 7 678
25 43 761
31 5 655
23 39 492
9 43 913
38 37 122
47 29 929
28 29 189
12 11 320
22 10 297
38 44 255
38 42 306
33 11 309
28 43 429
42 28 87
26 17 354
48 16 251
27 14 778
47 29 928
3 23 907
36 8 802
20 48 205
40 42 140
39 38 382
36 44 211
36 24 988
31 19 883
16 18 835
42 8 947
46 27 512
26 32 65
7 25 818
17 49 189
24 16 519
21 9 155
48 19 449
1 35 730
45 31 977
4 21 185
38 16 685
25 28 979
5 3 208
29 8 158
4 43 402
9 48 709
12 21 699
8 44 492
35 45 110
15 24 255
1 29 74
50 35 965
43 48 183
42 30 904
8 1 966
24 20 190
35 11 196
24 50 537
38 18 649
35 43 351
46 15 225
20 14 754
11 30 835
26 31 317
21 17 931
36 42 0
13 50 271
50 23 336
11 13 941
13 43 20
13 28 6
22 41 478
21 4 336
28 22 85
23 3 368
46 17 917
32 6 4
3 34 530
50 17 122
28 37 264
23 9 971
33 1 99
23 10 766
30 49 969
24 48 593
11 18 973
6 22 590
6 12 154
40 47 515
3 21 806
21 26 659
7 10 559
36 21 819
10 32 376
14 19 488
26 31 557
42 23 363
26 38 241
9 11 643
11 28 29
26 27 547
5 12 672
1 10 337
30 14 171
32 30 172
23 3 455
50 49 666
45 32 184
37 29 79
40 32 985
22 49 45
35 34 952
29 10 15
48 20 913
34 42 118
40 23 802
43 3 924
17 15 835
9 13 347
41 19 538
31 16 279
2 34 284
27 1 849
18 30 550
7 15 275
6 30 615
48 7 118
42 9 206
37 38 442
28 33 889
38 25 804
47 28 491
34 23 996
34 23 583
25 40 40
20 23 88
48 32 579
28 27 186
29 2 696
32 46 307
35 40 518
48 4 867
7 17 226
34 18 475
1 13 49
19 18 278
11 36 319
19 2 354
5 12 135
34 18 261
37 11 646
2 31 874
37 42 674
28 16 163
38 4 478
31 19 848
16 36 975
1 8 611
11 33 945
1 27 504
13 22 537
2 12 158
40 9 466
21 43 153
9 41 72
29 37 327
11 45 443
18 35 441
38 47 486
10 45 403
22 19 119
32 46 885
2 21 786
41 42 613
47 2 775
25 13 426
36 40 850
11 16 621
45 41 885
15 30 585
4 12 783
40 19 368
11 1 15
4 2 695
15 30 274
19 10 351
18 22 221
32 2 192
42 5 607
32 43 156
4 20 69
39 22 566
12 44 171
10 33 858
18 19 465
38 14 31
35 45 230
33 4 37
43 10 419
20 8 871
30 28 829
35 21 408
30 18 405
16 12 172
35 46 739
26 11 774
7 48 673
21 1 767
21 50 199
13 25 856
23 42 258
23 25 113
26 43 499
20 36 843
2 47 384
45 40 650
13 21 73
27 19 539
1 26 659
45 50 118
29 31 707
49 30 709
22 16 77
36 21 636
31 38 341
30 41 660
45 23 748
28 45 983
22 39 859
44 41 60
12 42 633
11 46 164
4 13 748
37 28 664
29 8 85
8 48 963
5 26 959
4 37 217
23 24 615
44 11 122
39 48 569
26 6 194
34 45 285
18 21 114
34 31 727
41 14 496
32 37 283
42 26 225
40 18 84
28 44 530
50 39 659
35 10 877
16 22 249
10 30 506
35 44 776
24 36 869
6 34 925
4 36 35
50 15 916
17 11 314
11 36 210
38 15 438
29 48 476
18 17 767
41 33 43
26 4 389
29 45 498
4 22 74
35 26 93
7 3 750
46 20 758
17 29 89
46 8 291
3 13 634
6 18 339
33 22 444
23 4 961
49 26 889
16 19 539
42 32 60
30 32 872
27 6 309
30 32 132
20 16 64
9 44 691
22 18 975
37 6 325
23 40 255
6 32 143
48 40 203
16 7 389
35 20 146
42 39 781
18 44 681
39 27 23
21 36 519
11 45 504
7 28 865
38 7 112
36 45 946
39 18 309
31 14 784
19 49 153
40 1 277
24 23 264
19 9 546
19 38 174
18 29 141
24 30 960
5 41 189
22 23 504
1 11 270
10 35 282
10 21 442
17 26 347
5 11 45
24 34 470
7 18 94
29 44 187
4 19 549
39 21 997
39 33 50
24 37 522
25 48 451
21 47 963
38 27 446
12 15 945
24 14 570
13 23 273
33 31 432
1 43 361
47 15 206
24 33 161
20 30 375
17 8 351
1 34 814
42 15 878
47 35 126
5 18 113
1 49 771
49 15 620
37 14 131
22 40 398
42 4 387
27 10 638
29 16 271
5 38 403
42 30 11
45 8 203
19 24 757
50 8 941
46 21 593
11 47 988
17 6 925
3 12 65
30 28 214
39 42 725
29 48 866
21 50 41
25 37 551
30 48 2
1 14 455
14 2 756
16 47 497
17 29 293
21 5 328
43 10 434
15 39 114
3 12 714
7 13 538
36 34 260
17 49 747
29 32 375
17 16 996
46 4 793
13 19 503
37 36 538
41 7 435
29 25 700
10 17 423
5 21 91
17 35 475
50 29 543
24 38 456
8 26 134
32 48 384
40 48 981
19 13 909
50 38 734
23 49 849
33 30 286
16 8 87
12 8 313
47 38 162
45 47 419
45 34 541
5 9 381
36 2 124
4 24 455
19 31 82
25 13 296
45 16 743
1 19 714
1 9 985
1 26 647
39 28 638
39 45 538
28 22 458
49 41 437
15 46 60
32 21 97
12 5 131
1 7 406
18 27 78
13 40 705
44 48 300
22 31 122
26 36 274
20 43 466
36 23 816
26 41 773
34 19 131
49 29 83
30 34 472
45 31 811
27 26 644
7 44 393
19 6 697
36 22 95
11 10 452
27 48 619
42 32 240
34 49 815
26 38 80
23 5 497
16 10 428
5 31 401
8 33 591
19 4 328
27 20 394
50 21 737
13 20 157
27 40 585
9 24 509
26 17 311
26 11 726
5 39 29
39 40 9
23 18 507
15 21 89
20 24 333
38 31 567
25 12 997
47 43 288
50 43 954
6 39 264
17 1 202
9 11 340
20 36 479
27 44 117
24 30 970
33 6 823
21 45 846
23 39 955
17 14 78
9 8 881
16 42 787
40 49 63
13 10 777
17 29 673
38 42 413
28 31 618
28 29 501
26 47 260
38 44 280
36 46 472
47 19 901
22 46 322
32 22 269
20 40 403
31 44 710
35 36 997
21 45 475
22 7 404
4 15 430
36 48 499
5 13 722
38 29 109
8 49 595
45 47 975
23 42 633
2 10 814
35 2 306
31 39 370
12 42 41
42 21 31
19 37 926
50 19 831
17 5 259
44 48 817
34 8 202
2 20 412
23 11 60
41 35 518
9 8 712
12 5 530
17 38 344
37 44 830
23 30 347
20 33 814
13 1 258
28 17 396
43 16 624
7 42 606
5 7 116
47 44 376
47 19 849
7 41 487
16 25 665
50 18 662
49 26 680
15 26 782
39 46 269
2 6 581
17 14 334
13 8 29
2 36 233
45 5 96
16 13 594
12 16 934
46 12 625
16 19 946
5 13 229
42 34 694
14 50 510
1 10 563
9 39 888
21 11 700
17 27 35
41 27 960
18 17 901
39 7 83
11 15 24
20 31 416
20 13 731
45 42 223
24 31 67
13 2 531
16 35 412
37 1 302
13 26 701
29 20 670
39 9 51
6 24 359
43 21 595
45 49 868
7 35 286
46 35 623
50 42 499
5 24 947
6 24 801
25 15 110
24 33 321
20 3 81
38 2 612
42 12 298
44 49 800
20 42 190
12 16 398
20 9 572
33 46 283
36 19 510
49 7 392
5 19 980
32 37 932
17 26 287
9 26 688
47 25 755
29 48 735
38 5 94
11 44 103
21 26 686
32 37 653
36 35 958
18 50 872
5 10 579
48 34 665
15 9 860
46 4 221
9 42 209
41 36 677
42 49 526
38 42 123
1 9 345
27 11 377
20 4 627
9 22 101
38 28 522
37 41 418
16 4 238
30 22 47
38 8 272
18 44 395
18 41 988
40 34 519
22 13 16
16 33 732
3 19 81
47 31 511
41 50 539
38 5 739
14 30 46
11 25 918
28 33 511
25 3 578
41 42 491
32 47 599
45 37 734
2 10 619
4 44 154
19 34 81
15 5 530
40 14 329
28 36 941
48 15 330
31 26 964
2 27 219
13 22 967
29 32 643
16 38 241
43 3 472
14 24 932
1 46 533
31 20 834
23 12 691
28 27 435
19 37 542
11 21 502
17 27 740
21 45 87
8 36 175
1 21 483
38 23 921
43 27 494
16 12 663
15 48 718
47 18 670
7 4 363
17 50 927
35 2 1
10 45 693
33 30 130
47 28 99
46 49 471
4 43 834
25 48 673
31 27 42
6 43 832
7 34 118
24 7 686
50 35 722
24 1 153
21 33 251
34 18 436
49 44 846
16 39 999
28 41 448
9 12 591
35 34 983
41 30 52
37 49 700
22 25 830
13 5 407
35 7 228
25 44 656
35 11 906
10 33 146
29 42 609
10 11 961
18 38 783
1 16 175
20 36 334
45 20 386
46 45 329
5 1 362
36 5 819
23 45 203
3 49 980
20 8 677
28 19 438
39 23 163
37 29 574
16 29 297
16 22 980
3 45 35
47 35 401
19 23 552
39 33 865
2 14 965
15 22 274
34 32 226
19 34 261
49 41 957
16 2 183
11 49 496
24 1 811
17 32 550
17 2 804
16 32 775
4 2 803
23 17 205
10 1 821
31 18 927
46 5 118
27 42 138
28 10 679
11 30 771
6 47 320
8 22 238
29 40 993
3 2 418
16 22 752
44 10 326
48 11 440
3 23 846
27 24 405
25 39 375
29 43 533
20 7 223
12 19 810
47 15 374
27 21 161
46 15 762
25 23 20
45 14 304
23 12 333
30 22 439
42 11 168
39 35 198
17 20 992
17 42 620
48 6 874
45 2 482
15 24 193
17 5 620
9 49 82
9 35 731
6 24 393
15 33 390
50 44 663
22 3 657
4 21 903
27 36 902
25 35 363
24 15 486
12 6 952
25 16 459
19 39 372
7 9 21
17 32 89
22 27 945
45 1 936
38 27 475
7 29 942
20 44 111
31 27 123
49 27 722
37 38 588
24 20 253
7 49 894
14 45 829
45 48 132
22 8 270
40 11 756
50 45 385
11 26 678
24 1 378
8 17 755
46 15 743
21 2 981
35 34 710
34 2 455
8 15 400
10 4 169
28 19 877
9 6 698
43 46 729
42 37 195
1 24 626
42 28 100
16 26 629
7 18 74
49 31 775
44 38 824
21 15 730
34 13 975
27 12 124
2 31 374
9 48 548
46 19 260
11 22 204
1 23 921
19 12 125
38 24 484
7 25 675
5 9 31
46 6 891
49 33 907
46 40 314
48 11 97
18 38 793
14 5 985
30 45 520
13 6 358
23 14 855
10 40 546
39 8 716
34 44 686
33 1 679
6 31 515
3 28 546
30 14 13
47 32 242
43 20 240
43 17 62
23 34 715
5 17 659
23 48 448
5 23 842
11 48 874
35 45 345
19 34 475
16 34 766
30 4 140
2 6 999
21 38 479
9 32 628
5 18 530
36 39 48
32 46 894
7 47 985
16 15 191
31 49 602
2 38 402
41 2 504
3 32 770
34 46 634
30 12 165
11 20 768
38 15 626
37 21 954
29 43 32
4 8 778
47 36 653
27 8 616
0

Output

Code: Select all

Network 1
The bandwidth is 17928.


damihp
New poster
Posts: 4
Joined: Thu Jul 11, 2013 12:58 am

Re: 820 - Internet Bandwidth

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.
Last edited by damihp on Wed May 14, 2014 2:52 am, edited 2 times in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 820 - Internet Bandwidth

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

4
1 4 11
3 2 695
2 1 174
3 4 687
4 3 162
3 1 625
3 2 338
3 1 263
4 1 608
4 1 505
2 4 882
1 2 43
3
2 1 12
2 1 177
1 2 379
3 2 182
3 1 480
3 2 857
2 1 687
1 2 822
3 1 774
2 1 659
1 3 190
2 3 74
2 1 931
7
7 1 8
4 7 666
2 6 102
7 4 883
3 2 732
2 3 505
5 2 854
1 2 148
1 3 399
0
Output

Code: Select all

Network 1
The bandwidth is 2218.

Network 2
The bandwidth is 4768.

Network 3
The bandwidth is 0.


damihp
New poster
Posts: 4
Joined: Thu Jul 11, 2013 12:58 am

Re: 820 - Internet Bandwidth

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
New poster
Posts: 2
Joined: Wed Jul 23, 2014 9:46 pm

Re: 820 - Internet Bandwidth

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
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 820 - Internet Bandwidth

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.

Post Reply

Return to “Volume 8 (800-899)”