文章

15

粉丝

446

获赞

2

访问

116.5k

头像
题没太看懂,写完记录一下
P1183 北京大学上机题
发布于2021年2月24日 16:22
阅读数 7.9k

#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;
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发