随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

hdu1102_Constructing Roads

        虽然这一题已经写过了,但是我觉得这里有问题。因为题目中有这样的一句话:
        We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
        这样一来,如果是A-B-C-D,我们能说A和D是相通的吗?我觉得不能,但是参考别人的代码时,他们都没有考虑这一中情况,我也写了一个没有考虑的。竟然过了!不知道为什么。我主要是在练习算法,难道是我理解错了?

#include <stdio.h>
#define DEBUG 1
const int Max = 0x7fffffff ;
const int N = 111 ;
int n, dis[N], used[N], closest[N], map[N][N] ;

int Prim( )
{
    
int i, j, index, min, len ;
    
for( i=1; i<=n; ++i ){
        used[i] 
= 0 ;
        dis[i] 
= map[1][i] ;
    }

    used[
1= 1 ;
    len 
= 0 ;
    
for( i=1; i<n; ++i ){
        min 
= Max ;
        
for( j=1; j<=n; ++j ){
            
if!used[j] && min>dis[j] ){
                index 
= j ;
                min 
= dis[j] ;
            }

        }

        used[index] 
= 1 ;
        len 
+= dis[index] ;
        
for( j=1; j<=n; ++j ){
            
if!used[j] && dis[j]>map[j][index] )
                dis[j] 
= map[j][index] ;
        }

    }

    
return len ;
}

int main()
{
    
#if DEBUG
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
     
#endif
     
    
int i, j, x, y, comp ;
    
while( EOF != scanf("%d"&n ) && n ){
        
for( i=1; i<=n; ++i ){
            
for( j=1; j<=n; ++j ){
                scanf(
"%d"&map[i][j] ) ;
                map[j][i] 
= map[i][j] ;
            }

        }

        scanf(
"%d"&comp ) ;
        
for( i=1; i<=comp; ++i ){
            scanf(
"%d%d"&x, &y ) ;
            map[x][y] 
= map[y][x] = 0 ;
        }

        printf(
"%d\n", Prim( ) ) ;
    }
                    
    
return 0 ;
}

posted on 2009-05-05 15:26 祝你好运! 阅读(264) 评论(1)  编辑 收藏 引用

评论

# re: hdu1102_Constructing Roads[未登录]  回复  更多评论   

无语了,也没说几组数据啊。。。。。。。。。。。。
2009-05-07 20:24 | 小白

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理