求MST两种算法：Prim和Kruskal。Prim以点作为主体，Kruskal以边作为主体。
#include <iostream>
#include <cmath>
using namespace std;
const int M=101;
const double MAX=10000000;
struct S
{
double x,y;
}data[M];
double map[M][M];
double dis[M]; //存储i节点到当前节点的最短距离
int n;
double res; //结果
double d(S a,S b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void prim(int v)
{
int i,j,t;
double min;
for(i=1;i<=n;i++)
dis[i]=map[v][i];
dis[v]=0; //标记已访问
res=0;
for(t=1;t<n;t++) //找点
{
min=MAX;
for(i=1;i<=n;i++)
if(dis[i]<min && dis[i]!=0) //找到未访问过的到当前节点最短的点
{
min=dis[i];
j=i;
}
res+=min;
dis[j]=0;
for(i=1;i<=n;i++) //更新dis数组
if(map[j][i]<dis[i])
dis[i]=map[j][i];
}
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%lf %lf",&data[i].x,&data[i].y);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=d(data[i],data[j]);
prim(1);
printf("%.2lf\n",res);
}
return 0;
}
posted on 2011-09-16 13:48
大大木马 阅读(246)
评论(0) 编辑 收藏 引用