求助
查看原帖
求助
260416
计算机彭耿鑫楼主2021/8/8 14:33
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1;
struct node
{
	int start,end;
	double len;
}m[maxn];
int l1[maxn],l2[maxn],l[maxn];
bool bmp(node a,node b)
{
	return a.len<b.len;
}
int find(int x)
{
	return l[x]==x?x:l[x]=find(l[x]);
}
int main()
{
	int a,b;
	cin>>a>>b;
	for(int i=1;i<=a;i++)
	cin>>l1[i]>>l2[i];	
	for(int i=1;i<=a;i++)
	l[i]=i;	
	int num=0,flag=a;
	int c,d;
	for(int i=1;i<=b;i++)
	{
		cin>>c>>d;
		int p=find(c);
		int q=find(d);
		if(p!=q)
		{
			l[p]=q;
			flag--;
		}
	}
	for(int i=1;i<=a;i++)
	{
		for(int j=i+1;j<=a;j++)
		{
			m[num].start=i;
			m[num].end=j;
			double p=(double)((l1[i]-l1[j])*(l1[i]-l1[j]));
			double q=(double)((l2[i]-l2[j])*(l2[i]-l2[j]));
			m[num++].len=(double)sqrt(p+q);
		}
	}
	sort(m,m+num,bmp);
	double hig=0;
	for(int i=0;i<num;i++)
	{
		int p=find(m[i].start);
		int q=find(m[i].end);
		if(p!=q)
		{
			l[p]=q;
			flag--;
			hig+=m[i].len;
		}
		if(flag==1)
		break;
	}
	printf("%.2lf",hig);
	return 0;
}
2021/8/8 14:33
加载中...