题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1821
为什么一群100ms的人啊….
n^2算出每两个点之间的距离，然后把这一堆边从小到大排序，只要两个端点不在一个部落里，并且目前的部落数大于需要的部落数，那么就合并
答案是部落数合法了之后找到的第一对不在同一部落的两点的距离
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<bits/stdc++.h> #define MAXN 1010 typedef double db; using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int x,y; int len; friend bool operator < (node a,node b){ return a.len<b.len; } }; int n,m; int xx[MAXN],yy[MAXN],tot,fa[MAXN]; node a[MAXN*MAXN]; int getroot(int x){ if(fa[x]==x)return x; return fa[x]=getroot(fa[x]); } int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++){ xx[i]=rd(); yy[i]=rd(); fa[i]=i; } for(int i=1; i<=n; i++){ for(int j=i+1; j<=n; j++){ a[++tot].x=i; a[tot].y=j; a[tot].len=(xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j]); } } sort(a+1,a+1+tot); for(int i=1; i<=tot; i++){ int x=getroot(a[i].x); int y=getroot(a[i].y); if(x==y)continue; if(n==m){ printf("%.2lf\n",sqrt(a[i].len*1.0)); return 0; } n--; fa[x]=y; } return 0; } |
