Detail of message

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

Re:Kruskal为什么老是Runtime Error?

Posted by willamette at 2005-08-17 02:02:54 on Problem 2421
In Reply To:Re:Kruskal为什么老是Runtime Error? Posted by:xfxyjwf at 2005-08-17 02:00:25

>  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~为什么?
> 
> 
> 
> 
汗.....
发错程序了
#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:

只要矩阵的上半边 (2775) xfxyjwf 2005-08-17 02:14:42
- 汗...过了 (0) willanthy 2005-08-17 02:17:23
ac了，快睡觉吧 (2668) frkstyc 2005-08-17 02:17:45
- 暂时不能......还得继续熟悉熟悉Prim.... (0) willamette 2005-08-17 02:18:50
  - 两个帐号这么相近,我还以为是同一个 (0) xfxyjwf 2005-08-17 02:23:55
    - 的确是有可能......不过如此人所言...我真得好好看看Prim..... (0) willanthy 2005-08-17 02:26:28
      - 显然是同一个人,我以为两个帐号是相同的,仔细一看,却不是:) (0) xfxyjwf 2005-08-17 02:28:32
        不对,你们到底几个人? (2) xfxyjwf 2005-08-17 02:29:34
        这个是我的GF的号码..........我得去看Prim了..不聊了...Crossing Edge不好选啊... (0) willanthy 2005-08-17 02:29:45
        幸福的人…… (0) frkstyc 2005-08-17 02:31:02
        enen,:) (0) xfxyjwf 2005-08-17 02:31:23
        不要老学我写"enen" (0) frkstyc 2005-08-17 02:31:58
        程序员的生活很单调的..... (0) willanthy 2005-08-17 02:32:36
        st觉得单不单调? (0) xfxyjwf 2005-08-17 02:34:09
        coder...显然的事情 (0) frkstyc 2005-08-17 02:35:25
        钱包和精神，选择哪样空虚呢？ (0) willanthy 2005-08-17 02:38:09
        neither (0) frkstyc 2005-08-17 02:39:46
        你都要了,是吧? (8) xfxyjwf 2005-08-17 02:40:42
        编程也是很有趣的啊,不然我们也不会熬到这么晚了. (0) xfxyjwf 2005-08-17 02:39:53
        我正在下SuperPower2.....外加编程.....把昨天留的题目继续K完 (0) willanthy 2005-08-17 02:40:53
        being a coder in real life is something very different (0) frkstyc 2005-08-17 02:40:58
        我们成为coder的可能性很小,至少我是这样认为的 (0) xfxyjwf 2005-08-17 02:42:21
        don't be over-optimistic, the competition could go beyond imagination (0) frkstyc 2005-08-17 02:43:57
        你都还没进CS,就一定成为coder了?大学也才上一年而已. (0) T3 2005-08-17 02:46:30
        开俩窗口,又用T3 re 了 (0) xfxyjwf 2005-08-17 02:48:16
        Coder的生活很悲惨的......和..一样靠青春吃饭.... (0) willamette 2005-08-17 02:44:23
        不了解....... (0) xfxyjwf 2005-08-17 02:47:17
        没经常关注过IT业？....俺们师兄、老师、外面BBS、报刊杂志都这么说的.... (0) willamette 2005-08-17 02:48:55
        Re:没经常关注过IT业？....俺们师兄、老师、外面BBS、报刊杂志都这么说的.... (18) Trident 2006-02-28 00:47:07
        最近很流行盖楼么？ (0) Qinz 2008-12-27 00:35:02
        我是来挖坟的。。。。 (9) lsdnlgd 2010-04-23 08:00:07
        Re:我是来挖坟的。。。。 (20) ycc1989918 2010-07-22 11:33:12
        Re:我是来挖坟的。。。。 (18) lxyxynt 2010-08-01 15:27:15
        Re:我是来挖坟的。。。。 (11) hqztrue 2011-06-03 16:40:16
        此楼要倒了。。 (0) bitchen 2011-06-15 15:56:04
        Re:此楼要倒了。。 (0) luyi0619 2011-06-25 14:12:49
        Re:此楼要倒了。。 (0) bobo0906 2011-07-10 17:38:41
        是的 (2) FreeDestiny 2011-08-27 14:26:13
        Re:是的此乃神楼。。 (15) dgsrz 2012-02-10 16:13:28
        Re:是的此乃神楼。。 (20) wang_125309 2012-02-25 12:25:18
        Re:是的此乃神楼。。 (5) peargobble 2012-03-19 19:16:13
        Re:是的此乃神楼。。 (7) peargobble 2012-03-19 19:16:29
        Re:是的此乃神楼。。 (9) 20101421 2012-06-24 10:27:20
        Re:是的此乃神楼。。 (17) 20101421 2012-06-24 10:28:04
        Re:是的此乃神楼。。 (30) cz908640443 2013-01-28 09:52:32
        Re:是的此乃神楼。。 (28) 3090101804 2013-02-15 19:41:34
        把楼歪一歪 (19) yygy 2014-07-04 21:21:08
        Re:把楼歪一歪 (0) bdf 2016-06-21 16:30:16
        Re:把楼歪一歪 (0) miubiu 2018-01-23 22:52:33
        Re:我来把快倒的楼盖正一下…… (0) lydliyudong 2012-06-24 14:00:41
        Re:我来把快倒的楼盖正一下……+1 (2) sidepi 2012-06-24 14:02:01
        Re:Coder的生活很悲惨的......和..一样靠青春吃饭.... (13) moxiaobei 2011-09-08 11:12:30
        太好用了,一学就会啊 (0) xfxyjwf 2005-08-17 02:32:58
        Re:太好用了,一学就会啊 (31) miluzhiyu 2009-07-18 01:45:38
        羡慕ing... (17) xfxyjwf 2005-08-17 02:32:38
        GF要我给她弄个账号炫耀一下.....汗...... (21) willanthy 2005-08-17 02:34:46
        Re:GF要我给她弄个账号炫耀一下.....汗...... (0) kongzyu 2019-01-19 17:34:55

Post your reply here:

User ID:
Password:
Title:

Content:

> 汗.....
> 发错程序了
> #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 ) ;
> }
> 
> 这个才是我的最终版本
> 在我们内部的服务器上测试正确

Home Page Go Back To top