Description
北极地区共有P座村庄，每座村庄均有自己的坐标。现在决定在村庄之间建立通信网络，其中通讯工具可以是无线电收发机，也可以是卫星设备。你的任务是让任意两座村庄之间都可以直接或间接地通信。
卫星设备一共有S台，拥有卫星设备的两座村庄之间无论相距多远都可以直接通信；其他每个村庄都可以配备一台无线收发机，但必须具有相同的参数d。只有欧基里德不是超过d的村庄才能用无线收发机直接通讯。由于d越大的无线电收发机越贵，你需要合理分配这S台卫星设备，才能让其他村庄的无线电收发机的d最小。
第一行为整数S,P，表示卫星通信设备数目和村庄数目。接下来的P行，每行表示一个村庄的坐标(x,y)。
Output
输出一个保留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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| 2 4
0 100
0 300
0 600
150 750
```
## Sample Output
```text
2 4
0 100
0 300
0 600
150 750
```
## 分析
当正向思考受阻时，逆向思维可能有奇效。本题就是这样。知道卫星设备的数量，求最小的收发距离，可能比较困难；如果知道距离求数量，就很简单了。把所有可以互相通讯的村庄连接起来，构成一个图。卫星设备的台数就是图的连通支的个数。
问题转化为：找到一个最小的d，使得把所有权值大于d的边去掉之后，连通支的个数小于等于k。
定理：如果去掉所有权值大于d的边后，最小生成树被分割成为k个连通支，图也被分割成为k个连通支。
{:.success}
证明：用反证法。假设原图被分割成k’ (k'≠k)个连通支，显然不可能k’>k，所以k’<k。因此在某一图的连通支中，最小生成树被分成了至少两部分，不妨设其为T1,T2。因为T1和T2同属于一个连通支，所以一定存在x∈T1，y∈T2，w(x,y)≤d。又因为在整个最小生成树中，所以x到y的路径中一定存在一条权值大于d的边(u,v)（否则x和y就不会分属于T1和T2了），w(x,y)≤d<w(u,v)，所以把(x,y)加入，把(u,v)去掉，将得到一棵总权值比最小生成树还小的生成树。这显然是不可能的。所以，原命题成立。（证毕）
有了这个定理，很容易得到一个构造算法：最小生成树的第k长边就是问题的解。
***——From 信息学奥赛一本通提高版***
## Codes
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <cmath>
#define maxn 1001
#define pf(x) (x*x)
using namespace std;
typedef long long ll;
struct node{
int a,b;
double val;
bool operator <(const node &obj)const{
return val<obj.val;
}
}g[maxn*maxn];
int tot,f[maxn];
double res[maxn];
pair<ll,ll> d[maxn]; int s,p;
inline double getdis(ll x1,ll x2,ll y1,ll y2){
return sqrt(pf(abs(x1-x2))+pf(abs(y1-y2)));
}
int Sfind(int x){
if(f[x]==x) return x;
else return f[x]=Sfind(f[x]);
}
inline void Sunion(int u1,int u2){
int fa=Sfind(u1);
int fb=Sfind(u2);
f[fa]=fb;
}
inline void makeEdge(){
for(int i=1;i<=p;i++)
for(int j=i+1;j<=p;j++)
g[++tot]=(node){i,j,
getdis(d[i].first,d[j].first,d[i].second,d[j].second)
};
}
double kruskal(){
int cnt=0;
sort(g+1,g+tot+1);
for(int i=1;i<=tot;i++){
if(Sfind(g[i].a)!=Sfind(g[i].b))
res[++cnt]=g[i].val,
Sunion(g[i].a,g[i].b);
}
return res[cnt-s+1];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
freopen("testout.txt","w",stdout);
#endif
cin>>s>>p;
if(s>=p){
cout<<"0.00";
return 0;
}
for(int i=1;i<=p;i++)
cin>>d[i].first>>d[i].second;
makeEdge(); for(int i=0;i<=p;i++) f[i]=i;
printf("%.2lf",kruskal());
return 0;
}
|
