这题乍看很吓人,其实就是一个贪心。
每次取最近的两个点所在的块合并,直到只剩下k块,输出答案。
/**************************************************************
Problem: 1821
User: zhuohan123
Language: C++
Result: Accepted
Time:136 ms
Memory:18492 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int f[];
int gf(int p){return p==f[p]?p:f[p]=gf(f[p]);}
struct point{double x,y;}p[];
double dis(point a,point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
struct edge
{
int from,to;double c;
friend bool operator<(edge a,edge b){return a.c<b.c;}
}g[];int gnum;
int main(int argc, char *argv[])
{
int n,k;scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=;i<=n;i++)f[i]=i;
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
{
g[++gnum].from=i;
g[gnum].to=j;
g[gnum].c=dis(p[i],p[j]);
}
sort(g+,g+gnum+);
for(int i=;i<=gnum;i++)
if(gf(g[i].from)!=gf(g[i].to))
{
if(n>k){f[gf(g[i].from)]=gf(g[i].to);n--;}
else {printf("%0.2lf\n",sqrt(g[i].c));return ;}
}
printf("0.00\n");
return ;
}