poj2031--Building a Space Station

題意：給你n個球 坐标 半徑。球若互相覆寫或接觸就算相連 讓你求出最小的長度使得從任意一球出發能到達任意球； 思路：最小生成樹 代碼用g++交WA 用c++就A 無語。。。 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <stdlib.h> #define N 110 #define INF 10000000 #define eps 10E-9//誤差 #define mem(a) memset(a,0,sizeof(a)) using namespace std; struct node { double x; double y; double z; double r; } ball[N]; double mmap[110][110]; double low[N]; int vis[N]; double dis(int x,int y)//球間距離 { double pd=sqrt((ball[x].x-ball[y].x)*(ball[x].x-ball[y].x)+(ball[x].y-ball[y].y)*(ball[x].y-ball[y].y)+(ball[x].z-ball[y].z)*(ball[x].z-ball[y].z)); double rr=ball[x].r+ball[y].r; if(pd>rr+eps) return pd-rr; return 0; } double prim(int n)//普利姆算法 { double result =0; int i,j,p; double mmin; memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); vis[0]=1; p=0; for(i=1; i<n; i++) { low[i]=mmap[p][i]; } for(i=1; i<n; i++) { mmin=INF; p=-1; for(j=0; j<n; j++) { if(mmin>low[j]&&0==vis[j]) { mmin=low[j]; p=j; } } if (INF == mmin) return -1; result+=mmin; vis[p]=1; for(j=0; j<n; j++) { if(0==vis[j]&&low[j]>mmap[p][j]) low[j]=mmap[p][j]; } } return result; } int main() { int n; int i,j,k; while(~scanf("%d",&n)&&n) { memset(mmap,0,sizeof(mmap)); for(i=0; i<n; i++) { scanf("%lf%lf%lf%lf",&ball[i].x,&ball[i].y,&ball[i].z,&ball[i].r); } for(i=0; i<n; i++)//建圖 for(j=i+1; j<n; j++) { mmap[i][j]=mmap[j][i]=dis(i,j); } double ans=prim(n); printf("%.3lf\n",ans); } return 0; }