bzoj ?1821: [JSOI2010]Group 部落划分 Group

 1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<queue> 6 #include<cmath> 7 #include<map> 8 using namespace std; 9 #define maxn 110000010 int n,m,k,x[maxn],cnt,y[maxn],tot; 11 int num,w[2333][2333],fa[maxn];12 double ans[maxn];13 struct Edge{14 ????int l,r;15 ????double w;16 }edge[maxn];17 18 char ch;19 inline void read(int &now)20 {21 ????ch=getchar(); now=0;22 ????while(ch>‘9‘||ch<‘0‘) ch=getchar();23 ????while(ch>=‘0‘&&ch<=‘9‘) now=now*10+ch-‘0‘,ch=getchar();24 }25 int find(int x) ???{ return fa[x]==x?x:fa[x]=find(fa[x]); }26 void add_edge(int l,int r)27 {28 ????edge[++num].l=l;29 ????edge[num].r=r;30 ????edge[num].w=sqrt(pow(x[l]-x[r],2)+pow(y[l]-y[r],2));31 }32 33 bool cmp(Edge a,Edge b) { return a.w<b.w; }34 bool cmp2(double a,double b) { return a>b; }35 int main()36 {37 // ???freopen("people.in","r",stdin);38 // ???freopen("people.out","w",stdout);39 ????read(n); read(k);40 ????for(int i=1;i<=n;i++) read(x[i]),read(y[i]);41 ????for(int i=1;i<=n;i++)42 ????????for(int j=i+1;j<=n;j++)43 ????????????add_edge(i,j);44 ????for(int i=1;i<=n;i++) fa[i]=i;45 ????sort(edge+1,edge+num+1,cmp);46 ????for(int i=1;i<=num;i++)47 ????{48 ????????int fx=find(edge[i].l),fy=find(edge[i].r);49 ????????if(fx!=fy)50 ????????{51 ????????????fa[fx]=fy;52 ????????????tot++;53 ????????????ans[++cnt]=edge[i].w;54 ????????????if(tot==n-1) break;55 ????????}56 ????}57 ????sort(ans+1,ans+n+1,cmp2);58 ????printf("%.2lf",ans[k-1]);59 ????return 0;60 }61 /*62 5 363 5 964 7 565 2 566 3 567 6 968 */