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

hdu1162_Eddy's picture

        题目就是给出一个笛卡尔坐标系,然后给出一些点,问题就是要求最小生成树。我以前没有做过这样的,因为这里,一个点到另一个点的距离没有给出。难道要把一个点到所有的点的距离都求出来?那样的话时间复杂度就太高了吧?
        我发现我现在还是太贪求速度,我确实是想到了这里,但是我没有去做,去写,而是去找别人的代码,先看看别人是怎么写的,然后我再写。其实,他们和我的算法思想是一样的。我以后要尽力改正这一个不好的习惯。这样非常不利于我学习算法。加油!

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

double Distance( double *a, double *b )
{
    
return sqrt( (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]) ) ;
}


double Prim( )
{
    
int i, j, index ;
    
double 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 ;
    
while( EOF != scanf("%d"&n ) ){
        
for( i=1; i<=n; ++i )
            
for( j=1; j<=n; ++j )
                map[i][j] 
= Max ;
        
for( i=1; i<=n; ++i )
            scanf(
"%lf%lf"&pos[i][0], &pos[i][1] ) ;
        
for( i=1; i<=n; ++i ){
            
for( j=i+1; j<=n; ++j ){
                map[i][j] 
= map[j][i] = Distance( pos[i], pos[j] ) ;
            }

        }

        printf(
"%.2lf\n", Prim( ) ) ;
    }

    
return 0 ;
}

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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理