YTU.1012: A MST Problem

YTU.1012: A MST Problem

1012: A MST Problem

题目描述

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

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 .

样例输入

221 1 02 2 031 2 30 0 01 1 1

样例输出

1.413.97

分析：3D空间上的最小生成树问题，

一个三维坐标点可以看成最小生成树的一个节点，那么三维空间里的点与点之间的距离就可以看成这两个节点间边的权重。

可以用结构体保存各个点的坐标x,y,z;

太菜了，没能写出来prim算法....还是继续用比较好写的kruskal算法吧。

#include#include#include#include#include 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>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<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算法：

#includeusing namespace std;#define maxn 35#define INF 999999double 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。