## 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

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

### 820 - Internet Bandwidth

I got WA on this problem.
I think the method is maximum flow.
Can you tell me what is the trick in this problem?

PdR
New poster
Posts: 24
Joined: Mon Dec 30, 2002 4:27 am

### Re: 820-Internet Bandwidth

There isn't really a trick, but you should attent this detail:
There might be more than one connection between a pair of nodes, but a node cannot be connected to itself.
This Input
2
1 2 2
1 2 10
1 2 20
0
Would obviously result in this Output:
Network 1
The bandwidth is 30.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
in my opinio thne outpuy should be...
Network 1
The bandwidth is 30.

Regrads.
MIras

BTW. tell me if i have a mistake...

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
Network 1
The bandwidth is 32.
not
Network 1
The bandwidth is 30.

sorry..

[/quote]

PdR
New poster
Posts: 24
Joined: Mon Dec 30, 2002 4:27 am
miras wrote: Network 1
The bandwidth is 32.
How could this be possible at all?
You have two connections between node 1 and 2 with capacities 10 and 20.
The maximum flow is 10+20.

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China
Thanks for your reply
I got AC now:)
I made a mistake in my code

FrodoBaggins
New poster
Posts: 2
Joined: Wed Apr 21, 2004 8:55 pm
Contact:
At first I seng this :
# include <stdio.h>

typedef struct List_
{
int Vertex ;
struct List_ * Previous , * Next ;
} List ;

int n , s , t ;
int h [ 120 ] , c [ 120 ] [ 120 ] , current [ 120 ] ;
int f [ 120 ] [ 120 ] , e [ 120 ] ;
List * Head = 0 , * Current = 0 ;

void Init ( void )
{
int i , j ;

for ( i = 1 ; i <= n ; i ++ )
{
h [ i ] = 0 ;
e [ i ] = 0 ;
for ( j = 1 ; j <= n ; j ++ )
f [ i ] [ j ] = 0 ;
}
h [ s ] = n ;
for ( i = 1 ; i <= n ; i ++ )
{
f [ s ] [ i ] = c [ s ] [ i ] ;
f [ i ] [ s ] = - c [ i ] [ s ] ;
e [ i ] = c [ s ] [ i ] ;
}
}

void Push ( int u , int v )
{
int d ;

d = e [ u ] < c [ u ] [ v ] - f [ u ] [ v ] ? e [ u ] : c [ u ] [ v ] - f [ u ] [ v ] ;
f [ u ] [ v ] += d ;
f [ v ] [ u ] = - f [ u ] [ v ] ;
e [ u ] -= d ;
e [ v ] += d ;
}

void Lift ( int u )
{
int i , min = - 1 ;

for ( i = 1 ; i <= n ; i ++ )
if ( ( h [ i ] < min || min == - 1 ) && c [ u ] [ i ] - f [ u ] [ i ] > 0 )
min = h [ i ] ;
h [ u ] = min + 1 ;
}

void Discharge ( int u )
{
int v ;

while ( e [ u ] > 0 )
{
v = current [ u ] ;
if ( v > n )
{
Lift ( u ) ;
current [ u ] = 1 ;
}
else
if ( c [ u ] [ v ] - f [ u ] [ v ] > 0 && h [ u ] == h [ v ] + 1 )
Push ( u , v ) ;
else
current [ u ] ++ ;
}
}

void AddList ( int i )
{
if ( ! Current )
{
Current = new List ;
Current -> Vertex = i ;
Current -> Next = Current -> Previous = 0 ;
Head = Current ;
return ;
}
Current -> Next = new List ;
Current -> Next -> Previous = Current ;
Current = Current -> Next ;
Current -> Vertex = i ;
Current -> Next = 0 ;
}

void ToHead ( void )
{
if ( Current == Head )
return ;
if ( Current -> Next )
Current -> Next -> Previous = Current -> Previous ;
Current -> Previous -> Next = Current -> Next ;
Current -> Next = Head ;
Head -> Previous = Current ;
Current -> Previous = 0 ;
Head = Current ;
}

void Preflow ( void )
{
int i , u , OldHeight ;

Init ( ) ;
for ( i = 1 ; i <= n ; i ++ )
{
current [ i ] = 1 ;
if ( i != s && i != t )
AddList ( i ) ;
}
Current = Head ;
while ( Current )
{
u = Current -> Vertex ;
OldHeight = h [ u ] ;
Discharge ( u ) ;
if ( h [ u ] > OldHeight )
ToHead ( ) ;
Current = Current -> Next ;
}
}

int main ( )
{
int i , j , u , v , a , r , test = 0 ;

scanf ( "%d" , & n ) ;
while ( n )
{
test ++ ;
for ( i = 1 ; i <= n ; i ++ )
for ( j = 1 ; j <= n ; j ++ )
c [ i ] [ j ] = 0 ;
scanf ( "%d%d%d" , & s , & t , & r ) ;
for ( i = 1 ; i <= r ; i ++ )
{
scanf ( "%d%d%d" , & u , & v , & a ) ;
c [ u ] [ v ] += a ;
c [ v ] [ u ] += a ;
}
Preflow ( ) ;
printf ( "Network %d\nThe bandwidth is %d.\n\n" , test , e [ t ] ) ;
scanf ( "%d" , & n ) ;
}
return 0 ;
}

and got WA
but when I insert this after input :
if ( s < t )
{
i = s ;
s = t ;
t = i ;
}
it got accepted
What's up?

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### 820 WA !!!! Help

Hi,
I'm getting lots of wa. I thinks its a simple max flow problem and implement it. But WA . Plz verify my code. Thanx in advance.

Code C++

Code: Select all

``````Cut After ACC....
``````
Please help me.
Last edited by Raj Ariyan on Wed Jun 15, 2005 6:18 pm, edited 1 time in total.
Some Love Stories Live Forever ....

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France

### hum hum

there is a small special point : reread the text
I've changed it in your code and I got Accepted P.E.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### 820

Hi Cytoplasm,
Thanx for ur reply. I'm confuced. There is no input where src==dst. Again one things may be happened that "There might be more than one connection between a pair of nodes", so i also checked it by the following code, but again got WA. Is there any other cases ?

Code: Select all

``````Cut after ACC...
``````
Last edited by Raj Ariyan on Sun Jun 19, 2005 8:31 am, edited 1 time in total.
Some Love Stories Live Forever ....

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France
src==dst
That's not a problem

"There might be more than one connection between a pair of nodes"
This is your problem, your new code is wrong.

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France
By the way I don'tunderstand that that:

Code: Select all

``````        f[u][v]+=max;
f[v][u]=-f[u][v];
``````
does work. I would have writen that instead:

Code: Select all

``````        f[u][v]+=max;
f[v][u]-=max;
``````
Does your code REALLY work or is it only luck if it's going through the judge tests?

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul
Hi Cytoplasm,
Yupe , u r rite. At first i wrote it, then i thought that flow in opsite direction is f[v]=-f[v], But i'm confuced that if more than one edge between two nodes, then i should take the max one, rite ? whats ur output for the following input ?

4
1 4 6
1 2 20
1 3 10
2 3 5
2 4 10
3 4 20
3 2 20
0
Last edited by Raj Ariyan on Sun Jun 19, 2005 8:36 am, edited 1 time in total.
Some Love Stories Live Forever ....

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France
For your entry, my solution is 30, and that's also the solution computed with my hands, so it should be correct.

I don't understand your problem, because it really IS simple and I won't give you the solution either because you would commit suicide for not having thought that yourself. So let's try to help you without giving you the key...

Let's say, you are trying to transport oil from city A to city B. In the first case there are two pipelines and in the second case there is only one pipeline. What should be the size of the single pipeline (of the 2nd case) to transport as much oil as the two pipelines (of the 1st case)?

Again, it is SIMPLE!

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### Problem

Hi Cytoplasm,
Thanx for ur help. I understand what u want to tell. AC at Last I've missed it. Again thanx. By the way can u check it -- > http://online-judge.uva.es/board/viewtopic.php?t=8301 Its a very easy problem but WA. What i miss ???? Bye and take care .
Some Love Stories Live Forever ....