WA 50pts 求调
查看原帖
WA 50pts 求调
933802
ICU152_lowa_IS8楼主2024/1/13 23:15

RT

#include<bits/stdc++.h>
using namespace std;
int father[1000005],num,head[100005];
struct node{
	int v,next,u;
	double w; 
}edge[10000005];
struct nde{
	double x,y;
}a[100005];
double sp(double x1,double y1,double x2,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void add(int u,int v,double w){
	edge[++num].next=head[u];
	head[u]=num;
	edge[num].w=w;
	edge[num].v=v;
	edge[num].u=u;
}
int find(int x){
	if(father[x]!=x)father[x]=find(father[x]);
	return father[x];
}
bool cmp(node a,node b){
	return a.w<b.w;
}
int main(){
	int n,m;
	cin>>n>>m;
	int cnt=1;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		father[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		father[x]=y;
		cnt++;
	}
	for(int x=1;x<=n;x++){
		for(int y=1;y<=n;y++){
			if(find(x)!=find(y)){
				add(x,y,sp(a[x].x,a[x].y,a[y].x,a[y].y));
				add(y,x,sp(a[x].x,a[x].y,a[y].x,a[y].y));
			}
		}
	}
	sort(edge+1,edge+num+1,cmp);
	double ans=0;
	for(int i=1;i<=num;i++){
		int fx=find(edge[i].u);
		int fy=find(edge[i].v);
		if(fx==fy)continue;
		ans+=edge[i].w;
		father[fx]=fy;
		cnt++;
		if(cnt==n)break;
	}
	printf("%.2lf",ans);
	return 0;
}

2024/1/13 23:15
加载中...