求大佬康康
查看原帖
求大佬康康
358793
想不好名字楼主2021/10/17 20:11
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std;

int n,m;
int f[110000];
int a[110000],b[110000];
struct edge{
	double u,v;
	double dis;
}e[100001];double ans;
int cnt,sum;

int find(int x){
	return x==f[x]?x:f[x]=find(x);
}
bool cmp(edge x,edge y){
	return x.dis<y.dis;
}
int main(){
//	freopen("未命名1.in","r",stdin);freopen("未命名1.out","w",stdout);
	scanf("%d%d",&n,&m);
	
	
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=1;j<i;++j){
			
			cnt++;
			e[cnt].u=i;
			e[cnt].v=j;
			e[cnt].dis=sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
		}
	}
	sort(e+1,e+cnt+1,cmp);
	for(int i=1;i<=m;++i) f[i]=i;
	for(int i=1;i<=cnt;++i){
		int X=find(e[i].u);int Y=find(e[i].v);
		if(X!=Y){
			f[X]=Y;
			sum++;
			ans=e[i].dis;
			ans=max(ans,e[i].dis);
		}
		if(sum>=m-n){
			printf("%.2lf",ans);
			fclose(stdin);fclose(stdout);
			return 0;
		}
	}
	printf("%.2lf",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}

40分,真的调不出来了

2021/10/17 20:11
加载中...