#include <stdio.h>
#include <algorithm>

struct edge
{
	int d, u, v;
}e[10010];
int n, m, r[2005];
int t, i, j, p, maxroad;

int cmp( const void *a, const void *b )
{
	return *(int *)a-*(int *)b;
}

int Top( int x )
{
	int t = x;
	while ( r[x]!=x )
		x = r[x];
	return r[t] = x;
}

int Union( int x, int y )
{
	int t1, t2;
	t1 = Top( x ); t2 = Top( y );
	if ( t1==t2 ) return 0;
	r[t1] = t2;
	return 1;
}

int main()
{
	while ( scanf( "%d%d", &n, &m )!=EOF )
	{
		for ( i=0; i<m; ++i )
			scanf( "%d%d%d", &e[i].u, &e[i].v, &e[i].d );
		qsort( e, m, sizeof( e[0] ), cmp );
		for ( i=0; i<=n; ++i )
			r[i] = i;
		i = 0; p = 0;
		while ( i<m && p<n-1 )
		{
			if ( Union( e[i].u, e[i].v ) )
				maxroad = e[i].d;
			++i;
		}
		printf( "%d\n", maxroad );
	}
	return 0;
}

• 我的47ms,只用了路径压缩这一个优化 (1284) fyq 2010-05-08 22:02:24