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