感觉学了这么久还是有那么一丢丢进步的...上个学期看到这道题，虽然早就学过并查集和二分了但还是一点思路都没有，现在可以秒切了呢

思路就是二分+并查集，有些人说是生成树，其实它没有变成树，只是运用了生成树的思想而已

分析

求距离最小的最大值，考虑二分

求距离那我们就二分距离吧

考虑check（）函数

显然如果我们当前的二分的距离为x，那么两点间的距离小于x的时候它们显然是在同一个部落里的，所以我们先按边权排序，然后枚举每条边的距离是否小于x，若小于就加入并查集更新，否则直接break退出

#include
    
     #pragma GCC optimize(3)#pragma GCC optimize(2)#pragma GCC optimize("Ofast")#include
     
      #include
      
       #include
       
        using namespace std;inline int read(){    int ans=0,f=1;char chr=getchar();    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}    return ans*f;}int n,m,tot,fa[1001],ans,l=0,r=100000000,mid;;struct P{int x,y;}a[1001];struct Q{int x,y,z;}t[1000001];inline int dist(int x1,int y1,int x2,int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}inline void add(int x,int y){t[++tot].x=x;t[tot].y=y;t[tot].z=dist(a[x].x,a[x].y,a[y].x,a[y].y);}bool operator < (const Q &x,const Q &y){return x.z
        
         x) break;        int fx=t[i].x,fy=t[i].y;        fx=find(t[i].x),fy=find(t[i].y);        if(fx==fy) continue;        fa[fx]=fy;    }int k=0;    for(int i=1;i<=n;i++) if(fa[i]==i) k++;    return k>=m;}int main(){    n=read();m=read();    for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();    for(int i=1;i<=n;i++)   for(int j=i+1;j<=n;j++) add(i,j);    sort(t+1,t+tot+1);    while(l<=r){        mid=l+r>>1;        if(check(mid)) l=mid+1;        else r=mid-1,ans=mid;    }return !printf("%.2f",sqrt(ans));}