首页 > 代码库 > poj2031(Building a Space Station)

poj2031(Building a Space Station)

2024-07-14 22:47:01   213人阅读

题目地址：Building a Space Station

 

题目大意：

     在一个三维的空间里有若干个球体，求从走过所有球花费最少，题目要求两个球体接触就不需要建桥意为花费为0，实力给吃的n行， 其中包括 球的X,Y,Z的坐标，r为球的半径。这里就清晰了，意思就是求无向图最小生成树，val就为两个求圆心的距离减去两个球的半径。

 

解题思路：

    建图，dijstra求最小生成树，记住双向的和eps处理精度。

 

代码：

  1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 31 /***************************************/ 32 void openfile() 33 { 34     freopen("data.in","rb",stdin); 35     freopen("data.out","wb",stdout); 36 } 37 priority_queue<int> qi1; 38 priority_queue<int, vector<int>, greater<int> >qi2; 39 /**********************华丽丽的分割线,以上为模板部分*****************/ 40 double map[200][200]; 41 int vis[200]; 42 double dis[200]; 43 int n; 44 struct N 45 { 46     double x,y,z,r; 47 } node[200]; 48 int EPS(double f) //处理精度问题 49 { 50     if (fabs(f)<eps) //e为科学计数法 51         return 0; 52     return f>0?1:-1; 53 } 54 double cha(int i,int j) 55 { 56     return sqrt((node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y)+(node[i].z-node[j].z)*(node[i].z-node[j].z))-node[i].r-node[j].r; 57 } 58 double dijstra() 59 { 60     int i,j,k; 61     for(i=1; i<=n; i++) 62     { 63         dis[i]=map[1][i]; 64         vis[i]=0; 65     } 66     vis[1]=1; 67     double sum=0; 68     for(i=2; i<=n; i++) 69     { 70         double min=INF; 71         for(j=1; j<=n; j++) 72             if (min>dis[j]&&!vis[j]) 73             { 74                 min=dis[j]; 75                 k=j; 76             } 77         vis[k]=1; 78         sum+=min; 79         for(j=1; j<=n; j++) 80             if (map[k][j]<dis[j]&&!vis[j]) 81                 dis[j]=map[k][j]; 82     } 83     return sum; 84 } 85 int main() 86 { 87  88     while(scanf("%d",&n)&&n) 89     { 90         int i,j; 91         for(i=0; i<=n; i++) 92             for(j=0; j<=n; j++) 93                 map[i][j]=INF; 94         for(i=1; i<=n; i++) 95             scanf("%lf%lf%lf%lf",&node[i].x,&node[i].y,&node[i].z,&node[i].r); 96         for(i=1; i<=n; i++) 97             for(j=1; j<=n; j++) 98             { 99                 if (i==j)100                     continue;101                 double ce=cha(i,j);102                 int ce1=EPS(ce);103                 if (ce>map[i][j])104                     continue;105                 if (ce1>0)106                 {107                     map[i][j]=ce;108                     map[j][i]=ce;109                 }110                 else111                 {112                     map[i][j]=0;113                     map[j][i]=0;114                 }115             }116         double cnt=dijstra();117         printf("%.3lf\n",cnt);118     }119     return 0;120 }
View Code

 


联系
我们