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

hdu1301_Jungle Roads

        这是我做的第一个最小生成树的题目。算法思想就是从任意一个点出发,标记为已找到的。然后找到所有与已找到的点相连的边中,权值最小的边。把边的另一个顶点标记为已找到的。然后更新所有与这个刚找到的顶点相邻的顶点的信息。重复这个步骤,直到找到了n-1个顶点。那就组成了一棵最小生成树,就是题目结束了。
#include <stdio.h>
#define DEBUG 1
const int Max = 0x7fffffff ;
const int N = 30 ;
int n, map[N][N], dis[N], used[N] ;

int Prim( )
{
    
int i, j, index, len, min ;
    len 
= 0 ;
    
for( i=1; i<=n; ++i ){
        
// 出发点定义为 1 
        dis[i] = map[1][i] ;
        used[i] 
= 0 ;
    }

    
// used[]数组作为标志 ,表示已经被标记过的点 
    used[1= 1 ;
    
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[index][j] )
                dis[j] 
= map[index][j] ;
        }

    }

    
return len ;           
}


int main()
{
    
//输入输出的重定向 
    #if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif
    
    
int i, j, d, geshu, weight ;
    
char ch, to ;
    
while( scanf("%d"&n) && n ){
        
//初始化数据 
        for( i=1; i<=n; ++i ){
            
for( j=1; j<=n; ++j ){
                map[i][j] 
= Max ;
            }

        }

        
//读入数据 
        for( i=1; i<n; ++i ){
            
//吃掉空格,不然机会造成读入数据错误 
            getchar() ;
            scanf(
"%c %d"&ch, &geshu ) ;
            
for( j=1; j<=geshu; ++j ){
                scanf(
" %c %d"&to, &weight ) ;
                
// -64 是为了把第一个点,也就是A点,当成第一个点
                 
// 因为A的ASCII是65 ,所以65-64 就是 1
                 
// 建立的是无向图 
                map[i][to-64= map[to-64][i] = weight ;
               }

        }

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

    
return 0 ;
}

posted on 2009-05-05 00:39 祝你好运! 阅读(211) 评论(0)  编辑 收藏 引用


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