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

Kruskal为什么老是Runtime Error?

Posted by willanthy at 2005-08-17 01:32:20 on Problem 2421 
#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 ) ;
}
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