> #include "stdio.h"
> #include "string.h"
> #include "stdlib.h"
> int tree[5100] , indep = 9999, l = 0;
> typedef struct vill
> {
> 	int *tree_index ;
> }VILL ;
> VILL vill[200] ;
> typedef struct road
> {
> 	int v , u ;
> 	int length ;
> }ROAD ;
> ROAD road[5100] ;
> int cmp ( const void *x , const void *y )
> {
> 	return (*(ROAD*)x).length - (*(ROAD*)y).length ;
> }
> void Kruskal_MST ( int num )
> {
> 	int i , k , sum = 0 , temp ;
> 	for ( i = 1 ; i <= num ; i ++ )
> 	{
> 		if ( vill[road[i].v].tree_index == &indep && vill[road[i].u].tree_index == &indep )
> 		{
> 			vill[road[i].v].tree_index = vill[road[i].u].tree_index = &tree[l++] ;
> 			sum = sum + road[i].length ;
> 		}
> 		else if ( *vill[road[i].v].tree_index != *vill[road[i].u].tree_index )
> 		{
> 			if ( vill[road[i].v].tree_index == &indep ) vill[road[i].v].tree_index = vill[road[i].u].tree_index ;
> 		 	else if ( vill[road[i].u].tree_index == &indep ) vill[road[i].u].tree_index = vill[road[i].v].tree_index ;
> 		 	else
> 			{
> 				temp = *vill[road[i].u].tree_index ;
> 				for ( k = 0 ; k < 5100 ; k ++ )
> 					if ( tree[k] == temp ) tree[k] = *vill[road[i].v].tree_index ;
> 			}
> 			sum = sum + road[i].length ;
> 		}
> 	}
> 	printf ( "%d\n" , sum ) ;
> }
> int main ( )
> {
> 	int i , j , k , n , temp , m , a , b , num ;
> 	freopen ( "2421.in" ,"r" , stdin ) ;
> 	freopen ( "2421.out" ,"w" , stdout ) ; 
> 	scanf ( "%d" , &n ) ;
> 	for ( i = 0 ; i < 5100 ; i ++ ) tree[i] = i;
> 	for ( i = 0 ; i < 200 ; i ++ ) vill[i].tree_index = &indep ;
> 	for ( i = 1 , k = 1 ; i <= n*n ; i ++ )
> 		for ( j = 1 ; j <= n ; j ++ )
> 		{
> 			scanf ( "%d" , &temp ) ;
> 			if ( i != j )
> 			{
> 				road[k].v = i ;
> 				road[k].u = j ;
> 				road[k].length = temp ;
> 				k ++ ;
> 			}
> 		}
> 	scanf ( "%d" , &m ) ;
> 	num = n * ( n + 1 ) / 2 ;
> 	while ( m -- )
> 	{
> 		scanf ( "%d" , &i ) ;
> 		scanf ( "%d" , &j ) ;
> 		if ( vill[i].tree_index == &indep && vill[j].tree_index == &indep )
> 			vill[i].tree_index = vill[j].tree_index = &tree[l++] ;
> 		else if ( (*vill[i].tree_index) != *vill[j].tree_index )
> 		{
> 			if ( vill[i].tree_index == &indep ) vill[i].tree_index = vill[j].tree_index ;
> 		 	else if ( vill[j].tree_index == &indep ) vill[j].tree_index = vill[i].tree_index ;
> 		 	else
> 			{
> 				temp = *vill[j].tree_index ;
> 				for ( k = 0 ; k < 5100 ; k ++ )
> 					if ( tree[k] == temp ) tree[k] = *vill[i].tree_index ;
> 			}
> 		}
> 	}
> 	qsort ( road , num , sizeof ( ROAD ) , cmp ) ;
> 	Kruskal_MST ( num ) ;
> }
> 

• going off... (0) frkstyc 2005-08-17 02:50:26
• 汗.....楼都盖这么高了 (0) willamette 2005-08-17 02:55:00
  • Re:汗.....楼都盖这么高了 (7) 00848164 2009-12-08 22:10:32