Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么我用Kruscal不对了??好心人帮我看看吧

Posted by JUSTACCEPTED at 2007-05-17 21:17:23 on Problem 2395
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator