- 题解
浇地
- @ 2026-8-3 11:55:33
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2010;
struct node {
int l,r,w;
} a[N*N];
int p[N],n,m,c,x[N],y[N];
int find(int k) {
if(p[k]!=k) return p[k]=find(p[k]);
return p[k];
}
bool cmp(node a,node b) {
return a.w<b.w;
}
long long kruskal() {
for(int i=1; i<=n; i++) p[i]=i;
long long ans=0,num=0;
for(int i=1; i<=m; i++) {
int pa=find(a[i].l),pb=find(a[i].r);
if(pa!=pb) {
p[pa]=pb;
ans+=a[i].w;
num++;
}
}
return num==n-1?ans:-1;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>c;
m=1;
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(i==j) continue;
int dist=((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
if(dist<c) continue;
a[m].l=i;
a[m].r=j;
a[m].w=dist;
m++;
}
}
sort(a+1,a+1+m,cmp);
cout<<kruskal();
return 0;
}
0 条评论
目前还没有评论...