| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么我用Kruscal不对了??好心人帮我看看吧#include<stdio.h>
typedef struct
{
int u ;
int v ;
long long dist ;
}PATH ;
PATH path[1024 * 10 ] ;
int father[1024 * 2 ] ;
int N , M ;
int Root( int v )
{
int f , t ;
f = v ;
while( f != father[f] )
{
f = father[f] ;
}
while( v != f )
{
t = father[v] ;
father[v] = f ;
v = t ;
}
return f ;
}
int cmp( const void * a , const void *b )
{
PATH *n = ( PATH *)a ;
PATH *m = ( PATH *)b ;
return n->dist > m->dist ;
}
int main()
{
int i , k , MaxDist = 0 , r1 , r2 ;
scanf("%d%d" , &N ,&M ) ;
for( i = 0 ; i <= N ; i++ )
{
father[i] = i ;
}
for( i = 0 ; i < M ; i++ )
{
scanf("%d%d%lld" , &path[i].u , &path[i].v , &path[i].dist ) ;
}
qsort( path , M , sizeof( PATH ) , cmp ) ;
for( i = 0 , k = 0 ; i < M && k != N - 1 ; i++ )
{
r1 = Root( path[i].u ) ;
r2 = Root( path[i].v ) ;
if( r1 != r2 )
{
father[path[i].v] = path[i].u ;
if( MaxDist < path[i].dist )
{
MaxDist = path[i].dist ;
}
k++ ;
}
}
printf("%lld\n" , MaxDist ) ;
}
return 0 ;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator