 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
ac了，快睡觉吧In Reply To:Re:Kruskal为什么老是Runtime Error? Posted by:willamette at 2005-08-17 02:02:54 > 汗.....
> 发错程序了
> #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 )
> {
> long 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 ( "%ld\n" , sum ) ;
> }
> int main ( )
> {
> long i , j , k , n , temp , m , a , b , num ;
> freopen ( "2421.in" ,"r" , stdin ) ;
> freopen ( "2421.out" ,"w" , stdout ) ;
> scanf ( "%ld" , &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 ; i ++ )
> for ( j = 1 ; j <= n ; j ++ )
> {
> scanf ( "%ld" , &temp ) ;
> if ( i != j )
> {
> road[k].v = i ;
> road[k].u = j ;
> road[k].length = temp ;
> k ++ ;
> }
> }
> scanf ( "%ld" , &m ) ;
> num = n * ( n + 1 ) / 2 ;
> while ( m -- )
> {
> scanf ( "%ld" , &i ) ;
> scanf ( "%ld" , &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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
