820 - Internet Bandwidth

[sunhong]

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]

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]

in my opinio thne outpuy should be...

Network 1
The bandwidth is 30.

Regrads.
MIras

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

[miras]

Network 1
The bandwidth is 32.

not

Network 1
The bandwidth is 30.

sorry..

[/quote]

[PdR]

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]

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

[FrodoBaggins]

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]

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.

[Cytoplasm]

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

[Raj Ariyan]

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


[Cytoplasm]

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]

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]

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

[Cytoplasm]

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]

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 .