POJ2031

题目大意是建立空间站的通路，要求包括所有空间站，每个站点给定空间坐标和半径，问至少需要建立通路的长度。

方法：prime算法建立最小生成树即可。经过将近半天的查找错误，终于发现G++和C++一点不同：

1.数据位是double型时，G++使用scanf函数输入需要用%lf,printf函数输出用%f

2.C++不同，scanf和printf都使用%lf即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double inf=1000.0;
const int maxn=105;
const double eps=1e-10;
double mapp[maxn][maxn];
double dis[maxn];
int vis[maxn];
int n;
double ans;
struct node
{double x;double y;double z;double r;
} pp[maxn];
void init()
{for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mapp[i][j]=inf;memset(vis,0,sizeof(vis));ans=0;
}
int EPS(double k)
{if(fabs(k)<eps)return 0;return k>0?1:-1;
}
void maketree()
{double dist,disx,disy,disz,disr;for(int i=1; i<=n; i++)for(int j=n; j>=i; j--){double temp=sqrt((pp[i].x-pp[j].x)*(pp[i].x-pp[j].x)+(pp[i].y-pp[j].y)*(pp[i].y-pp[j].y)+(pp[i].z-pp[j].z)*(pp[i].z-pp[j].z))-pp[i].r-pp[j].r;if(EPS(temp)<=0)///这里可能精度不够mapp[i][j]=mapp[j][i]=0;elsemapp[i][j]=mapp[j][i]=temp;}
}
void prime()
{for(int i=1; i<=n; i++)dis[i]=mapp[1][i];dis[1]=0;vis[1]=1;for(int v=0; v<n-1; v++){double minx=inf;int p=-1;for(int i=1; i<=n; i++)if(!vis[i]&&dis[i]<minx){p=i;minx=dis[i];}vis[p]=1;ans+=dis[p];for(int i=1;i<=n;i++)if(!vis[i]&&dis[i]>mapp[p][i])dis[i]=mapp[p][i];}
}
int main()
{while(scanf("%d",&n)){if(n<=0)break;init();for(int i=1; i<=n; i++)scanf("%lf%lf%lf%lf",&pp[i].x,&pp[i].y,&pp[i].z,&pp[i].r);maketree();prime();printf("%.3lf\n",ans);}return 0;
}