Steven_MengのBlog

传送门

这题其实有两种做法:

$1.$
我一开始想到的是二分加并查集,考虑二分最近部落的距离,如果两点$i$,$j$距离小于等于$mid$那么连边,并查集维护,最后统计有多少集合。
考虑如何证明单调性:如果两点$i$,$j$在$mid1$情况下能连边,那么在$mid2$情况下也能连边($mid2>mid1$),那么$mid1$情况下的集合数不可能小于$mid2$情况下的集合数
这样我们可以愉快地二分答案。

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
62
63
64
65
66
#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
int fa[MAXN];
inline void Init(){
for (register int i=0;i<MAXN;++i){
fa[i]=i;
}
}
int Fa(int i){
return fa[i]==i?i:fa[i]=Fa(fa[i]);
}
inline void Union(int i,int j){
fa[Fa(i)]=Fa(j);
}
};
using namespace BCJ;
int x[MAXN],y[MAXN];
inline double Dist(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int n,k;
inline bool Check(double mid){
Init();
for (register int i=1;i<=n;++i){
for (register int j=1;j<=n;++j){
if (Dist(i,j)<=mid){
Union(i,j);
}
}
}
int ans=0;
for (register int i=1;i<=n;++i){
if (fa[i]==i) ans++;
}
return ans>=k;
}
int main(){
Init();
n=read(),k=read();
for (register int i=1;i<=n;++i){
x[i]=read(),y[i]=read();
}
double l=0,r=0x7fffffff;
const double eps=1e-4;
while (l+eps<r){
double mid=(l+r)/2.0;
if (Check(mid)) l=mid;
else r=mid;
}
printf("%.2lf\n",l);
}

$2.$
考虑连边过程中集合数的变化,发现多连一条边,集合数就会减一。
要让最后有$k$个集合,$yy$一下,发现要连$n-k+1$条边,于是我们可以用一个类似于$Kruskal$的贪心,只不过加到$n-k+1$条边就退出。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
int fa[MAXN];
inline void Init(){
for (register int i=0;i<MAXN;++i){
fa[i]=i;
}
}
int Fa(int i){
return fa[i]==i?i:fa[i]=Fa(fa[i]);
}
inline void Union(int i,int j){
fa[Fa(i)]=Fa(j);
}
};
using namespace BCJ;
struct Edge{
int u,v;
double w;
}G[MAXN*2];
inline bool operator < (const Edge &A,const Edge &B){
return A.w<B.w;
}
int tot;
inline void AddEdge(int u,int v,double w){
G[++tot].u=u,G[tot].v=v,G[tot].w=w;
}
double x[MAXN],y[MAXN];
#define Pow(a) a*a
inline double dis(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
inline double Kruscal(int MaxE){
Init();
sort(G+1,G+1+tot);
int E=0;
for (register int i=1;i<=tot;++i){
if (Fa(G[i].u)!=Fa(G[i].v)){
Union(G[i].u,G[i].v);
E++;
if (E==MaxE){
return G[i].w;
}
}
}
}
int main(){
int n=read(),k=read();
for (register int i=1;i<=n;++i){
x[i]=(double)read();
y[i]=(double)read();
}
for (register int i=1;i<n;++i){
for (register int j=i+1;j<=n;++j){
AddEdge(i,j,dis(i,j));
}
}
printf("%.2lf\n",Kruscal(n-k+1));
}

p.s被$double$孙了甚久。

 评论