题目描述
It is just a mining spanning tree ( 最小生成树 ) problem, what makes you a little difficult is that you are in a 3D space.
输入
The first line of the input contains the number of test cases in the file. And t he first line of each case
contains one integer numbers n(0<n<30) specifying the number of the point . The n next n line s, each line
contain s Three Integer Numbers xi,yi and zi, indicating the position of point i.
输出
For each test case, output a line with the answer, which should accurately rounded to two decimals .
样例输入
|
1 2 3 4 5 6 7 8 |
2 2 1 1 0 2 2 0 3 1 2 3 0 0 0 1 1 1 |
样例输出
|
1 2 |
1.41 3.97 |
分析：3D空间上的最小生成树问题，
一个三维坐标点可以看成最小生成树的一个节点，那么三维空间里的点与点之间的距离就可以看成这两个节点间边的权重。
可以用结构体保存各个点的坐标x,y,z;
因为好久没写过prim算法，遇到点问题，用kruskal提交AC。
kruskal算法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<iostream> #include<stdio.h> #include<algorithm> #include<math.h> #include<memory.h> using namespace std; const int maxn=35; double mp[maxn][maxn]; int f[maxn]; typedef struct { int x; int y; int z; } ZB; ZB a[maxn]; typedef struct { int x; int y; double w; } QQ; QQ b[maxn]; bool cmp(QQ a,QQ b) { return a.w<b.w; } int findx(int x) { int r=x; while(r!=f[r]) r=f[r]; return r; } int main() { int t,n; cin>>t; while(t--) { cin>>n; for(int i=1; i<=n; i++) { cin>>a[i].x>>a[i].y>>a[i].z; f[i]=i; } memset(mp,0,sizeof(mp));//初始化 double len; for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { len=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)); mp[i][j]=mp[j][i]=len;//构造邻接矩阵 } } // for(int i=1;i<=n;i++) // { // for(int j=1;j<=n;j++) // { // cout<<mp[i][j]<<" "; // } // cout<<endl; // } int q=0; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { if(j>i) { q++; b[q].x=i; b[q].y=j; b[q].w=mp[i][j]; } } sort(b+1,b+q+1,cmp); int p=0; double ans=0; for(int i=1; i<=q; i++) { if(findx(b[i].x)!=findx(b[i].y)) { ans+=b[i].w; f[findx(b[i].x)]=b[i].y; p++; if(p==n-1) break; } } printf("%.2lf\n",ans); } return 0; } |
prim算法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<bits/stdc++.h> using namespace std; #define maxn 35 #define INF 999999 double graph[maxn][maxn];//邻接矩阵 double dist[maxn];//距离 bool vis[maxn]; typedef struct{ int x; int y; int z; }ZB; ZB a[maxn]; int N; double prim() { int pos=1; double ans,Min; memset(vis,0,sizeof(vis)); ans=0; for(int i=1;i<=N;i++) { dist[i]=graph[pos][i];//与pos邻接点的距离 } vis[pos]=1; for(int i=2;i<=N;i++) { Min=INF; pos=-1; for(int j=1;j<=N;j++) { if(!vis[j]&&Min>dist[j]) { Min=dist[j]; pos=j; } } if(pos==-1) return -1; vis[pos]=1; ans+=Min; for(int j=1;j<=N;j++) { if(!vis[j]&&dist[j]>graph[pos][j])//执行更新，如果点距离当前点的距离更近，就更新dist dist[j]=graph[pos][j]; } } return ans; } int main() { int t,n; cin>>t; while(t--) { cin>>n; N=n; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) { graph[i][j]=INF;//初始化均不可达 } for(int i=1; i<=n; i++) { cin>>a[i].x>>a[i].y>>a[i].z; } double len; for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { len=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)); graph[i][j]=graph[j][i]=len;//构造邻接矩阵 } } printf("%.2lf\n",prim()); } return 0; } |
Post a new comment