我是 zz 吗这么简单都写错......
一眼二分, 然后判断的话是枚举点, 然后计算这个点到已有联通块的最小距离, 如果这个点到一些联通块的距离小于当前二分的 val, 则把这些联通块合并起来, 这里用并查集维护, 最后看这样得出的部落数是否大于 k(多出来的可以直接合并)
有个非常小的优化就是不用 double 二分, 直接把点两两之间的距离存起来排个序, 直接在排序后数组里二分即可
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<vector>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=1005;
- int n,m,x[N],y[N],f[N],tot;
- double mn[N],d[N*N];
- int read()
- {
- int r=0,f=1;
- char p=getchar();
- while(p>'9'||p<'0')
- {
- if(p=='-')
- f=-1;
- p=getchar();
- }
- while(p>='0'&&p<='9')
- {
- r=r*10+p-48;
- p=getchar();
- }
- return r*f;
- }
- double dis(double x1,double y1,double x2,double y2)
- {
- return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
- }
- int zhao(int x)
- {
- return x==f[x]?x:f[x]=zhao(f[x]);
- }
- bool ok(double va)
- {
- int col=0;
- for(int i=1;i<=n;i++)
- f[i]=i;
- for(int i=1;i<=n;i++)
- {
- int s=0,w;
- for(int j=1;j<=n;j++)
- mn[j]=1e9;
- for(int j=1;j<i;j++)
- {
- int nw=zhao(j);
- mn[nw]=min(mn[nw],dis(x[i],y[i],x[j],y[j]));
- }
- for(int j=1;j<i;j++)
- if(f[j]==j&&mn[j]<va)
- s++,w=j;
- if(s>1)
- {
- for(int j=1;j<i;j++)
- if(f[j]==j&&mn[j]<va&&j!=w)
- f[j]=w;
- f[i]=w;
- }
- else if(s==1)
- f[i]=w;
- }
- for(int i=1;i<=n;i++)
- if(f[i]==i)
- col++;
- // printf("%.2lf %d\n",va,col);
- // for(int i=1;i<=n;i++)
- // cerr<<zhao(i)<<" ";
- // cerr<<endl;
- return col>=m;
- }
- int main()
- {
- n=read(),m=read();
- for(int i=1;i<=n;i++)
- {
- x[i]=read(),y[i]=read();
- for(int j=1;j<i;j++)
- d[++tot]=dis(x[i],y[i],x[j],y[j]);
- }
- sort(d+1,d+1+tot);
- int l=0,r=tot,ans;
- while(l<=r)
- {
- int mid=(l+r)>>1;
- if(ok(d[mid]))
- l=mid+1,ans=mid;
- else
- r=mid-1;
- }
- printf("%.2lf\n",d[ans]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2706002.html