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

hdu1233_还是畅通工程

          没什么好说的,还是最小生成树,和上一题一样,没有任何变化。我现在只会prim算法,所以就只用prim写。

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

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

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

        }

        used[index] 
= 1 ;
        len 
+= dis[index] ;
        
for( j=1; j<=n; ++j ){
            
if!used[j] && dis[j]>map[index][j] ){
                closest[j] 
= index ;
                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, x, y, weight, hangshu ;
    
while( scanf("%d"&n) && n ){
        
for( i=1; i<=n; ++i ){
            
for( j=1; j<=n; ++j ){
                map[i][j] 
= Max ;
            }

        }

        hangshu 
= n*(n-1)/2 ;
        
for( i=1; i<=hangshu; ++i ){
            scanf(
"%d%d%d"&x, &y, &weight ) ;
            map[x][y] 
= map[y][x] = weight ;
        }

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

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


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