求B题思路

1、二分答案之后秒
2、把所有的距离排序之后用并查集秒

dp, O(n^3)

贪心不知道对不对 坐等结果。。。

+1

直接贪心吧。。。 二分干么呢。。。

实际上不用殡查己吧
只要知道有多少对点的距离超过t 就行了吧

按s排序 并查集 贪心

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
double x[1000],y[1000],z[1000];
double d[1000][1000];
int root[1000];
inline double sqr(double x) { return x*x; }
int f(int x) { return root[x]==x?x:root[x]=f(root[x]); }
void u(int x, int y) { root[f(x)] = root[f(y)]; }
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>x[i]>>y[i]>>z[i];
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
d[i][j] =sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]);
double l = 0, r = 1.0+1e-5;
while(r-l>1e-7)
{
double mid = (l+r)/2;
for(int i=0;i<n;i++) root[i] = i;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if (d[i][j]<=mid) u(i,j);
set<int> s;
for(int i=0;i<n;i++) s.insert(f(i));
if (s.size()>=k) l=mid; else r=mid;
}
if (l>1.0) l = 1.0;
printf("%.6f\n",l);
return 0;
}


O(n^2 log(n))的复杂度。。。
有点悬~~

二分查找都可以的？

我是先求所有的差度值,然后取第N(网页)-K(类数)+1个值,但一直内存读写错误,到最后还是wa,已到点了

格式怎么贴成这鸟样了..
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
double x[1000],y[1000],z[1000];
double d[1000][1000];
int root[1000];
inline double sqr(double x) { return x*x; }
int f(int x) { return root[x]==x?x:root[x]=f(root[x]); }
void u(int x, int y) { root[f(x)] = root[f(y)]; }
int main()
{
　　int n,k;
　　cin>>n>>k;
　　for(int i=0;i<n;i++)
　　　　cin>>x[i]>>y[i]>>z[i];
　　for(int i=0;i<n;i++)
　　　　for(int j=i+1;j<n;j++)
　　　　　　d[i][j] = sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j]);
　　double l = 0, r = 1.0+1e-5;
　　while(r-l>1e-7)
　　{
　　　　double mid = (l+r)/2;
　　　　for(int i=0;i<n;i++) root[i] = i;
　　　　for(int i=0;i<n;i++)
　　　　　　for(int j=i+1;j<n;j++)
　　　　　　　　if (d[i][j]<=mid) u(i,j);
　　　　set<int> s;
　　　　for(int i=0;i<n;i++) s.insert(f(i));
　　　　if (s.size()>=k) l=mid; else r=mid;
　　}
　　if (l>1.0) l = 1.0;
　　printf("%.6f\n",l);
　　return 0;
}