## 820 - Internet Bandwidth

Moderator: Board moderators

### 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?
sunhong
New poster

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

### 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.
PdR
New poster

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

in my opinio thne outpuy should be...
Network 1
The bandwidth is 30.

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]
miras
Learning poster

Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

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.
PdR
New poster

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

I got AC now:)
I made a mistake in my code
sunhong
New poster

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

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 ;
return ;
}
Current -> Next = new List ;
Current -> Next -> Previous = Current ;
Current = Current -> Next ;
Current -> Vertex = i ;
Current -> Next = 0 ;
}

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

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

Init ( ) ;
for ( i = 1 ; i <= n ; i ++ )
{
current [ i ] = 1 ;
if ( i != s && i != t )
}
while ( Current )
{
u = Current -> Vertex ;
OldHeight = h [ u ] ;
Discharge ( u ) ;
if ( h [ u ] > OldHeight )
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?
FrodoBaggins
New poster

Posts: 2
Joined: Wed Apr 21, 2004 8:55 pm

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

Last edited by Raj Ariyan on Wed Jun 15, 2005 6:18 pm, edited 1 time in total.
Some Love Stories Live Forever ....
Raj Ariyan
Learning poster

Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### hum hum

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

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

### 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 ....
Raj Ariyan
Learning poster

Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

src==dst
That's not a problem

"There might be more than one connection between a pair of nodes"
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?
Cytoplasm
New poster

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

Hi Cytoplasm,
Yupe , u r rite. At first i wrote it, then i thought that flow in opsite direction is f[v][u]=-f[u][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 ....
Raj Ariyan
Learning poster

Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

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!
Cytoplasm
New poster

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

### 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 ....
Raj Ariyan
Learning poster

Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Next