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

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

分析

考虑check()函数

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

#include<cstdio>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cmath>
#include<algorithm>
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<y.z;}
int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);}
inline bool check(int x){
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=tot;i++){
if(t[i].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));
}
05-11 22:34