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

Post by sunhong » Sun Apr 11, 2004 1:21 pm

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

Post by PdR » Sun Apr 11, 2004 9:32 pm

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

Post by miras » Tue Apr 13, 2004 12:07 pm

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

Regrads.
MIras

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

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

Post by miras » Tue Apr 13, 2004 12:08 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

Post by PdR » Tue Apr 13, 2004 4:27 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.

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

Post by sunhong » Wed Apr 14, 2004 2:48 pm

Thanks for your reply
I got AC now:)
I made a mistake in my code :cry:

FrodoBaggins
New poster
Posts: 2
Joined: Wed Apr 21, 2004 8:55 pm
Contact:

Post by FrodoBaggins » Wed Apr 21, 2004 9:03 pm

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

Post by Raj Ariyan » Sat Jun 11, 2005 5:37 pm

Hi,
I'm getting lots of wa. I thinks its a simple max flow problem and implement it. But WA :cry: . 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

Post by Cytoplasm » Tue Jun 14, 2005 6:36 pm

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

Post by Raj Ariyan » Wed Jun 15, 2005 7:29 am

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

Post by Cytoplasm » Wed Jun 15, 2005 9:57 am

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

Post by Cytoplasm » Wed Jun 15, 2005 10:26 am

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

Post by Raj Ariyan » Wed Jun 15, 2005 10:38 am

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

Post by Cytoplasm » Wed Jun 15, 2005 5:03 pm

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

Post by Raj Ariyan » Wed Jun 15, 2005 6:16 pm

Hi Cytoplasm,
Thanx for ur help. I understand what u want to tell. AC at Last :lol: 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 ....

Post Reply

Return to “Volume 8 (800-899)”