The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2560-Freckles 最小生成树

今天碰到一个最小生成树(数据结构基础算法)
巩固了一下 没有什么大的收获。

不过发现原来在程序后面加个system("pause")也能AC;
代码如下:
#include <iostream>
#include
<algorithm>
#include
<cmath>
using namespace std;
#define  MAX 101
#define INFINITE 1000000000

struct node
{
    
double a;
    
double b;
}
dot[MAX];

double value[MAX][MAX];
bool visit[MAX];
double dis[MAX];
int n;

double distance(int i,int j)
{
    
double temp=0;
    temp
=sqrt((dot[i].a-dot[j].a)*(dot[i].a-dot[j].a)+(dot[i].b-dot[j].b)*(dot[i].b-dot[j].b));
    
return temp;
}


double  prim()
{
    
double sum=0;
    
int i,j;
    
int k;
    memset(visit,
false,sizeof(visit));
    
for(i=1;i<=n;i++)
    
{

        dis[i]
=value[1][i];
    }

    visit[
1]=true;
    
int mark;
    
double test=10000000000;
    sum
=0;
    
for(j=1;j<=n-1;j++)
    
{
        test
=INFINITE;
        
for(i=1;i<=n;i++)
        
{
            
if(visit[i]==false&&dis[i]<test)
            
{

                test
=dis[i];
                mark
=i;
            }

            
        }

        sum
+=test;visit[mark]=true;
        
for(i=1;i<=n;i++)
        
{

            
if(visit[i]==false&&value[mark][i]<dis[i])
                dis[i]
=value[mark][i];

        }

    }

    
return sum;
}








    
int main ()
    
{
        
int i,j;
        scanf(
"%d",&n);
        
for(i=1;i<=n;i++)
        
{

            scanf(
"%lf%lf",&dot[i].a,&dot[i].b);
        }

        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{

                value[i][j]
=distance(i,j);
            }


        }

        printf(
"%.2f\n",prim());
        system(
"pause");
        
return 0;
}


posted on 2009-02-22 20:30 abilitytao 阅读(1557) 评论(2)  编辑 收藏 引用

评论

# re: POJ 2560-Freckles 最小生成树 2010-05-21 23:02 zybest

郁闷,老是wa,能给点测试数据吗  回复  更多评论   

# re: POJ 2560-Freckles 最小生成树 2010-05-21 23:23 abilitytao

@zybest
你可以比对下我的程序看看自己思路的那个环节出问题了。  回复  更多评论   


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