Sol: 一个并查集的简单题, 将边权从小到大排序, 然后尽量让小边连的点放到一个集合中.
- #include<bits/stdc++.h>
- #define N 1000005
- using namespace std;
- struct ppp {
- int x,y,v;
- } a[500005];
- bool cmp(ppp a,ppp b) {
- return a.v<b.v;
- }
- int f[1005],x[1005],y[1005],tot,n,k,xx,yy;
- int get(int x) {
- return f[x]==x?x:f[x]=get(f[x]);
- }
- int main() {
- 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++)
- {
- tot++;
- a[tot].x=i;
- a[tot].y=j;
- a[tot].v=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
- }
- sort(a+1,a+tot+1,cmp);// 将边权从小到大排序
- for (int i=1; i<=n; i++)
- f[i]=i;
- for (int i=1; i<=tot; i++)
- // 取出边来, 尽量让小边所连的点, 放在同一个部落中
- {
- xx=get(a[i].x);
- yy=get(a[i].y);
- if (xx!=yy)
- // 最开始 N 个点分成 N 个集合, 如果不在一个集合, 则合并起来
- // 集合个数减少一个
- {
- n--;
- f[xx]=yy;
- if (n<k)
- // 这里理解清楚, 当集合个数小于 k 时, 则说明当前已分成了 K 个集合了
- // 当前的边就是答案了
- {
- printf("%.2lf",sqrt(a[i].v));
- return 0;
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3456331.html