- 题解
浇地
- @ 2026-8-3 11:55:11
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2010; struct node { int l,r,w; } a[NN]; 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 numn-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(ij) 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; }