文章
15
粉丝
446
获赞
2
访问
122.7k
#include<bits/stdc++.h>
#define MAXINT 32767
using namespace std;
typedef long long ll;
struct node{
double x;
double y;
};
double dist(node a,node b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
bool isTrue(bool a[100],int n)
{
bool tag=true;
for(int i=0;i<n;i++)
if(!a[i])
tag=false;
return tag;
}
void Prim(node a[100],int n)
{
bool b[100];
double dis=0;
for(int i=0;i<n;i++)
b[i]=false;
b[0]=true;
while(!isTrue(b,n))//检测是否所有点都已经连接
{
double mds=MAXINT;
int v;
for(int i=0;i<n;i++)从已连接集合中选一点
{
if(b[i])
{
for(int j=0;j<n;j++)//从未连接集合选一点
if(b[j]==false&&mds>dist(a[i],a[j]))
{
mds=dist(a[i],a[j]);//找最小的边
v=j;//保存点
}
}
}
dis+=mds;//加入距离
b[v]=true;//加入集合
}
printf("%.2lf\n",dis);
return;
}
int main()
{
int n;
while(cin>>n)
{
node a[100];
for(int i=0;i<n;i++)
cin>>a[i].x>>a[i].y;
...
登录后发布评论
暂无评论,来抢沙发