P1991 无线通讯网

题目描述

国防部计划用无线网络连接几个边防哨所。 用于构建无线网络的不同通信技术；

每个边防哨所都应配备无线电收发器；有些哨所还可以配备卫星电话。

无论他们相距多远，任何两个配备卫星电话线的哨所（两边都有卫星电话）都可以通话。只有无线电收发器通话的哨所之间的距离不得超过DD，这是受收发器功率限制的。收发器功率越高，通话距离越远DD会更远，但同时价格会更贵。

收发器需要统一购买和安装，所以所有哨所只能选择安装一种型号的收发器。换句话说，每个哨所之间的通话距离都是一样的DD。您的任务是确定收发器必要的最小通话距离DD，使每对哨所之间至少有一条通话路径(直接或间接)。

输入格式

从 wireless.in 输入数据第 1 行，2 个整数SS和PP，SS表示可安装卫星电话的哨所数，PP表示边防哨所的数量。接下里PP行，每行两个整数x，yx，y描述哨所的平面坐标(x, y)(x,y)，以 km 为单位。

输出格式

输出 wireless.out 中

第 1 行，1 个实数DD，表示无线电收发器的最小传输距离，精确到小数点后两位。

输入输出样例

输入 #1复制

2 4 0 100 0 300 0 600 150 750 

输出 1复制

212.13

说明/提示

对于 20\%20% 的数据：P = 2，S = 1P=2，S=1

对于另外 20\%20% 的数据：P = 4，S = 2P=4，S=2

对于 100\%100% 的数据保证：1 ≤ S ≤ 1001≤S≤100，S < P ≤ 500S

思路

1、赤裸裸的最小生成树模板（参考上一题）

2、s！没用！

3、先求一个最小生成树，其中的最大边就是没有所谓的“卫星电话”时的答案了。

4、和最小生成树的区别就是退出条件：最小生成树的模板，有n - 1条边就可以退出了，这里退出条件变成了p - s(p和之前的n是几乎一样的)。（s的唯一一点用处，所以不用考虑那么多卫星电话啥啥的）

（因为有卫星电话的（s个站），人家可以直接联系）

代码

#include 
using namespace std;
int s,p,n,total,a[100000],b[100000];
struct edge{
    int start;
	int to;
	double val;
}bian[2000000];
int f[1000000];
double ans;
int find(int x)//并查集部分
{
    if (f[x]==x) 
		return x; 
	else 
    {
        f[x]=find(f[x]);
        return f[x];
    }	
}

bool cmp(edge a,edge b)//结构体排序,这个排法太赞了！！ 
{
    return a.val>s>>p;
    for(int i=1;i<=p;i++) 
		f[i]=i;//初始化父节点为自己 
    for(int i=1;i<=p;i++)//存图 !!
    {
    	cin>>a[i]>>b[i];
    	for(int j=1;j