hdu1162-Eddy's picture

http://acm.hdu.edu.cn/showproblem.php?pid=1162

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std; 

#define MAX 5050
int fa[ MAX ] ;
struct node
{
	int x , y ;
	double value ;
	bool operator < (const node &T) const
	{
		return value < T.value;
	} 
}edge[ MAX ]; 

struct point
{
	double x , y ;
}point[ MAX ];

int Union( int n ) 
{
	for( int i = 0 ; i < n ; ++i )
		fa[ i ] = i ;
}
int find( int x ) 
{
	return fa[ x ] = x == fa[ x ] ? x : find( fa[ x ] ) ;
}

int main()
{
	int n ;
	int i , j ;
	while( scanf( "%d" , &n )!= EOF && n )
	{
		Union( n * n ) ;
		for( i = 0 ; i < n ; ++i )
		{
			scanf( "%lf%lf" , &point[ i ].x , &point[ i ].y ) ;
		}
		int k = 0 ;
		for( i = 0 ; i < n ;  ++i )
		{
			for( j = i + 1 ; j < n ; ++j )
			{
				edge[ k ].x = i ;
				edge[ k ].y = j ;
				edge[ k ].value = (double )sqrt( ( point[ i ].x - point[ j ].x ) * ( point[ i ].x - point[ j ].x ) + ( point[ i ].y - point[ j ].y )*(point[ i ].y - point[ j ].y ) );
				
					k++ ;	
			
			}
		}
		sort( edge , edge + k ) ;
		double sum = 0.0 ;
		for( i = 0 ; i < k ; ++i )
		{
			
			int x1 = find( edge[ i ].x ) ;
			int x2 = find( edge[ i ].y );
			if( x1 != x2 )
			{
				sum += edge[ i ].value ;
				fa[ x1 ] = x2 ;
			}
		}
		printf( "%.2lf\n" , sum ) ;
	}
	return 0 ;
}