图论 | 最小生成树 | 北极通讯网络

Description

北极地区共有P座村庄,每座村庄均有自己的坐标。现在决定在村庄之间建立通信网络,其中通讯工具可以是无线电收发机,也可以是卫星设备。你的任务是让任意两座村庄之间都可以直接或间接地通信。
卫星设备一共有S台,拥有卫星设备的两座村庄之间无论相距多远都可以直接通信;其他每个村庄都可以配备一台无线收发机,但必须具有相同的参数d。只有欧基里德不是超过d的村庄才能用无线收发机直接通讯。由于d越大的无线电收发机越贵,你需要合理分配这S台卫星设备,才能让其他村庄的无线电收发机的d最小。

Input

第一行为整数S,P,表示卫星通信设备数目和村庄数目。接下来的P行,每行表示一个村庄的坐标(x,y)。

Output

输出一个保留2位小数的实数,表示最小的无线电收发器半径。

Sample Input

2 4 
0 100 
0 300 
0 600 
150 750 

Sample Output

2 4 
0 100 
0 300 
0 600 
150 750 

分析

当正向思考受阻时,逆向思维可能有奇效。本题就是这样。知道卫星设备的数量,求最小的收发距离,可能比较困难;如果知道距离求数量,就很简单了。把所有可以互相通讯的村庄连接起来,构成一个图。卫星设备的台数就是图的连通支的个数。
问题转化为:找到一个最小的d,使得把所有权值大于d的边去掉之后,连通支的个数小于等于k。

定理:如果去掉所有权值大于d的边后,最小生成树被分割成为k个连通支,图也被分割成为k个连通支。

证明:用反证法。假设原图被分割成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

#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;
}