1、題目類型：計算幾何，最小生成樹。

2、解題思路：（1）獲得所有點路徑長度的矩陣map[][]；（2）利用Prim算法求解最小生成樹。

3、注意事項：數學操作，中間值全部用double保存。

4、實現方法:

#include<iostream>
#include<cmath>
#include<algorithm>
#define _Max 10000000
#define _Min 0.00000000001
using namespace std;

struct Node
{
double x,y,z;
double r;
};

Node Arr[101];
int n;
double map[101][101],dis[101],ans;
bool visted[101];

double Lengh(Node A,Node B)
{
double x=(A.x-B.x)*(A.x-B.x);
double y=(A.y-B.y)*(A.y-B.y);
double z=(A.z-B.z)*(A.z-B.z);
if((sqrt(x+y+z)-A.r-B.r)>_Min)
return sqrt(x+y+z)-A.r-B.r;
else
return 0;
}

void Init()
{
for(int i=1;i<=n;i++)
cin>>Arr[i].x>>Arr[i].y>>Arr[i].z>>Arr[i].r;
for(int j=1;j<=n;j++)
for(int k=j;k<=n;k++)
map[j][k]=map[k][j]=Lengh(Arr[j],Arr[k]);
ans=0.0;
}

void Prim()
{
int i,j;
memset(visted,0,sizeof(visted));
for(i=1;i<=n;i++)
dis[i]=map[1][i];
visted[1]=1;
dis[1]=_Max;
for(i=1;i<n;i++)
{
int pos=min_element(dis+1,dis+n+1)-dis;
ans+=dis[pos];
visted[pos]=1;
dis[pos]=_Max;
for(j=1;j<=n;j++)
{
if(dis[j]>map[pos][j]&&!visted[j])
dis[j]=map[pos][j];
}
}
}

int main()
{
while(cin>>n&&n)
{
Init();
Prim();
printf("%.3f\n",ans);
}
return 0;
}

?

轉載于:https://www.cnblogs.com/yongze103/archive/2010/07/29/1788013.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Building a Space Station--POJ 2031的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。