求助!!代码哪里有问题
查看原帖
求助!!代码哪里有问题
377876
lbc20070331楼主2022/7/18 18:51
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+233;
struct tree{
	int x,y;
	double z;
};
tree t[maxn];
struct node{
	int x,y;
};
node a[maxn];
int fa[maxn];
bool cmp(tree d,tree f){
	d.z<f.z;
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0',c=getchar();
	}
	return x*f;
}
int main()
{
	int n,m;
	int cnt=1;
	n=read(),m=read();
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].x >> a[i].y;
		for (int j = 1; j < i; j++)
		{
			t[cnt].z = sqrt(1.0 * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1.0 * (a[i].y - a[j].y) * (a[i].y - a[j].y));
			t[cnt].x = i, t[cnt].y = j;
			cnt++;
		}
		fa[i] = i;
	}
	sort(t+1,t+cnt,cmp);
	double sum=0.00;
	for(int i=1;i<=m;i++){
		int u,v;
		u=read(),v=read();
		if(find(u)!=find(v)) fa[find(u)]=find(v);
	} 
	for(int i=1;i<cnt;i++){
		int u=t[i].x;
		int v=t[i].y;
		if(find(u)!=find(v)){
			fa[find(u)]=find(v);
			sum+=t[i].z;
			m++;	
		}
	}
	cout << fixed << setprecision(2) << sum;
	return 0;
}
2022/7/18 18:51
加载中...