最小生成树

概念:将图中所有顶点连结，并且使边的总权值最小所形成的树。

算法：

1：初始化一个点a，并把a加入候选点数组point[]中，将所有可能与a相连的点列于数组array；

2：在array中选边<a，array[]>的权值最小的边<a，array[i]>；

3：在图中找权值比array中还小的边替代array中的边；

3：循环1，2步骤；

例题（来自：http://acm.hdu.edu.cn/showproblem.php?pid=1162）

做这道题时，我自己的测试数据没通过。我就认为是刚用的0x7fffffff 即int形的最大值在某个部分溢出了。这个想法本来就不可能发生，因为我没给它做运算，只是作比较用的，并且我的变量时double的不可能超出那么多啊！我真笨。然后我又用输出函数看每一阶段的结果，太不小心，没考虑函数对整体的影响。最后才发现是比较最大值时的初始化位置不对。

我做这题是有点着急了，手工的步骤没写好就写程序，以至于写得非常慢。

这个算法的用途是形成一个权值最小且覆盖整个图的树即最小生成树的定义。

例题：（hdu1162）

#include<stdio.h>

#include<math.h>

#include<string.h>

double date[101][2];

double distance(double ax,double ay,double bx,double by)

{

return sqrt(pow(ax-bx,2)+pow(ay-by,2));

}

double count(int n)

{

int i,j,now,temp;

double mintree[101],min,dis;

bool sign[101];

memset(sign,1,sizeof(sign));//初始化标记

now=0;

sign[0]=false;

for(i=0;i<n;i++)

mintree[i]=0x7fffffff;//初始化最小生成树

for(i=0;i<n;i++){

temp=now;

min=0x7fffffff;

for(j=0;j<n;j++){

if(min>mintree[j]&&sign[j]){//找下一个扩展点

min=mintree[j];

temp=j;

}

}

now=temp;/////////////////////////////替换当前点

sign[now]=false;//////////////////////标记以经扩展的点

for(j=0;j<n;j++){

dis=distance(date[j][0],date[j][1],date[now][0],date[now][1]);//刷新备选树

if(dis<mintree[j]&&sign[j]){

mintree[j]=dis;

}

}

}

dis=0;

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

dis+=mintree[i];

return dis;

}

main()

{

int n;

int i;

while(scanf("%d",&n)!=-1){

for(i=0;i<n;i++)

scanf("%lf%lf",&date[i][0],&date[i][1]);

printf("%.2lf/n",count(n));

}

return 0;

}