并查集水题
假设刚开始一个点就是一个部落
然后合并两两距离最小且不是同一部落，直到k
然后就完啦
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<map> #include<algorithm> using namespace std; int n,k; int xi[1005],yi[1005]; int fa[1005]; struct data { int ai,bi; double vi; }d[500005]; int cnt=0,op; bool cmp(data x,data y) { return x.vi<y.vi; } inline int find(int x) { if(fa[x]==x)return x; else return fa[x]=find(fa[x]); } int main() { int i,j,l,r; scanf("%d%d",&n,&k); for(i=1;i<=n;i++){ scanf("%d%d",&xi[i],&yi[i]); fa[i]=i; } op=n; for(i=1;i<n;i++) for(j=i+1;j<=n;j++){ cnt++; d[cnt].vi=sqrt((xi[i]-xi[j])*(xi[i]-xi[j])+(yi[i]-yi[j])*(yi[i]-yi[j])); d[cnt].ai=i; d[cnt].bi=j; } sort(d+1,d+1+cnt,cmp); for(i=1;i<=cnt;i++){ l=find(d[i].ai); r=find(d[i].bi); if(l!=r){fa[l]=r;op--;} if(op<k)break; } printf("%.2lf",d[i].vi); while(1); return 0; }