10pts求助
查看原帖
10pts求助
707616
whb569楼主2022/11/23 17:51
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int s[1005],n,m,cur;
double x[1005],y[1005];
double ans=0.0;
struct node{
	int x;
	int y;
	double dis;
}edges[50001000];
int find(int x)
{
	return s[x]==x?x:s[x]=find(s[x]);
}
double dist(double x1,double y1,double x2,double y2)
{
	return (double)sqrt((abs(x1-x2)*abs(x1-x2))+(abs(y1-y2)*abs(y1-y2)));
}
bool cmp(node a,node b)
{
	return a.dis<b.dis;
}
int main()
{
	int a,b,ic=0;
	cin>>n>>m;
	for(int i =1;i<=n;i++)s[i]=i;
	for(int i =1;i<=n;i++)cin>>x[i]>>y[i];
	for(int i =1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			edges[ic].x=i;edges[ic].y=j;edges[ic].dis=dist(x[i],x[j],y[i],y[j]);
			ic++;
		}
	}
	for(int i =0;i<m;i++)
	{
		cin>>edges[ic].x>>edges[ic].y;
		edges[ic].dis=0.0;
		ic++;
	}
	ic--;
	sort(edges,edges+ic,cmp);
	for(int i=0;i<=ic;i++)
	{
		int x1=find(edges[i].x);int y1=find(edges[i].y);
		if(x1==y1)continue;
		ans+=edges[i].dis;
		s[x1]=y1;
		cur++;
		if(cur==n-1)break;
	}
	printf("%.2lf",ans);
	return 0;
}
2022/11/23 17:51
加载中...