BZOJ 1821 [JSOI2010] Group 部落划分 Group

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vector>typedef long long LL;using namespace std;const int maxn=2100;int n,k,x[maxn],y[maxn],tot;double ans;struct edge{ ???int u,v; ???double w; ???friend bool operator <(const edge&a,const edge &b) { ???????return a.w<b.w; ????}}e[1005*1005];double dis(int a,int b) { ???return sqrt((double)(x[a]-x[b])*(x[a]-x[b])+(double)(y[a]-y[b])*(y[a]-y[b]));}int fa[maxn];int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}void kruskal() { ???sort(e+1,e+tot+1); ???for(int i=1;i<=n;i++) fa[i]=i; ???int cnt=0; ???for(int i=1;i<=tot;i++) { ???????int u=e[i].u,v=e[i].v; ???????int fu=find(u),fv=find(v); ???????if(fu!=fv) { ???????????cnt++; ???????????if(cnt==n-k+1) { ???????????????ans=e[i].w; ???????????????break; ???????????} ???????????fa[fu]=fv; ???????} ???}}int main(){ ???//freopen(".in","r",stdin); ???//freopen(".out","w",stdout); ???scanf("%d%d",&n,&k); ???for(int i=1;i<=n;i++) ????????scanf("%d%d",&x[i],&y[i]); ???for(int i=1;i<=n;i++) ????????for(int j=i+1;j<=n;j++) { ???????????e[++tot].u=i; ???????????e[tot].v=j; ???????????e[tot].w=dis(i,j); ???????} ???kruskal(); ???printf("%.2lf\n",ans); ???return 0;}