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

## low expectation is a way of living of mine

Posted by frkstyc at 2005-08-17 02:50:09 on Problem 2421
In Reply To:Kruskal为什么老是Runtime Error? Posted by:willanthy at 2005-08-17 01:32:20
```> #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] ;
> {
> 	int v , u ;
> 	int length ;
> int cmp ( const void *x , const void *y )
> {
> }
> void Kruskal_MST ( int num )
> {
> 	int i , k , sum = 0 , temp ;
> 	for ( i = 1 ; i <= num ; i ++ )
> 	{
> 		{
> 			sum = sum + road[i].length ;
> 		}
> 		{
> 		 	else
> 			{
> 				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 )
> 			{
> 				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 ) ;
> }
>
```

Followed by: