7,9,10 wa了
查看原帖
7,9,10 wa了
559503
j_steady楼主2022/4/26 20:22
#define int long long

using namespace std;

int n,m;
int fa[200005];
struct edge{
	int u,v,w;
}e[300005];
long long ans;
int maxn=-114;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
int cnt=0;
void add(int u,int v,int w){
	e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w;
}
void init(){
	for(int i=1;i<=n;i++) fa[i]=i;
}
int find (int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void play(int x,int y){
	
}
bool cmp(edge x,edge y){
	return x.w<y.w;
}
int ojld(int x1,int y1,int x2,int y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
struct node{
	int xx,yy;
}ab[300005];

signed main (){
	n=read(),m=read();
	init();
	for(int i=1;i<=n;i++){
		ab[i].xx=read(),ab[i].yy=read();
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int dis=ojld(ab[i].xx,ab[i].yy,ab[j].xx,ab[j].yy);
			if(dis<m) continue;
			add(i,j,dis);
		}
	}
	int t=0;
	sort(e+1,e+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		int fx=find(e[i].u),fy=find(e[i].v);
		if(fx==fy) continue;
		fa[fx]=fy;
		ans+=e[i].w;
	}
	int cntt=0;
	for(int i=1;i<=cnt;i++){
		if(fa[i]==i)  cntt++;
	}
	if(cntt>1) puts("-1");
	else printf ("%lld",ans); 
	return 0;
} 
2022/4/26 20:22
加载中...