蒟蒻WA 40分求助awa
查看原帖
蒟蒻WA 40分求助awa
188104
StObOtZ楼主2021/7/15 20:57
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	double x,y,z;
}f[500001];
int k,sum,fa[1005],a[1005],b[1005];
double ans;
inline int read(){
	int x=0,m=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') m=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*m;
}
inline void write(int x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
inline bool cmp(node a,node b){
	return a.z<b.z;
}
inline int find(int x){
	if (fa[x]=x)	return x;
	fa[x]=find(fa[fa[x]]);
	return fa[x];
} 
inline bool check(int x,int y){
	x=find(fa[x]);
	y=find(fa[y]);
	if (x==y)	return true;
		else return false;
}
inline void ad(int x,int y){
	x=find(fa[x]);
	y=find(fa[y]);
	fa[x]=y;
}
signed main(){
	int n=read(),m=read();
	for (int i=1;i<=m;i++){
		a[i]=read(),b[i]=read();
		for (int j=1;j<i;j++){
			f[++k].z=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
			f[k].x=i;
			f[k].y=j;
		}
	}
	for (int i=1;i<=m;i++)	fa[i]=i;
	sort(f+1,f+k+1,cmp);
	for (int i=1;i<=k;i++){
		if (!check(f[i].x,f[i].y)){
			ad(f[i].x,f[i].y);
			ans=f[i].z;
			sum++;
			if (sum>=m-n){
				printf("%.2lf",ans);
				return 0;
			}
		}
	}
}
2021/7/15 20:57
加载中...