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?
I think the method is maximum flow.
Can you tell me what is the trick in this problem?
Re: 820-Internet Bandwidth
There isn't really a trick, but you should attent this detail:
This InputThere might be more than one connection between a pair of nodes, but a node cannot be connected to itself.
Would obviously result in this Output:2
1 2 2
1 2 10
1 2 20
0
Network 1
The bandwidth is 30.
-
- 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?
# 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?
-
- 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++
Please help me.
I'm getting lots of wa. I thinks its a simple max flow problem and implement it. But WA
![:cry:](./images/smilies/icon_cry.gif)
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 ....
-
- 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 ?
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 ....
By the way I don'tunderstand that that:
does work. I would have writen that instead:
Does your code REALLY work or is it only luck if it's going through the judge tests?
Code: Select all
f[u][v]+=max;
f[v][u]=-f[u][v];
Code: Select all
f[u][v]+=max;
f[v][u]-=max;
-
- 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 ?
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 ....
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!
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!
-
- 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 .
Thanx for ur help. I understand what u want to tell. AC at Last
![:lol:](./images/smilies/icon_lol.gif)
Some Love Stories Live Forever ....