[BZOJ1821][JSOI2010]部落划分

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

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

分析

考虑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));

}