算法
最小生成树+瓶颈生成树
思路
瓶颈生成树
定义无向图G，G的瓶颈生成树是一棵 “ 树上最大边权值 edge 在G的所有生成树中最小 ” 的生成树，这样的生成树可能不止一棵。瓶颈生成树的值为树上最大边权值 edge
最小生成树是瓶颈生成树的充分不必要条件。
命题：最小生成树一定是瓶颈生成树。
证明：可以采用反证法予以证明。
假设最小生成树不是瓶颈树，设最小生成树T的最大权边为e，则存在一棵瓶颈树Tb，其所有的边的权值小于w(e)。删除T中的e，形成两棵树T', T''，用Tb中连接T', T''的边连接这两棵树，得到新的生成树，其权值小于T，与T是最小生成树矛盾。 [1]
命题：瓶颈生成树不一定是最小生成树。
下面是一个反例：
Kruskal算法（克鲁斯卡尔算法）
Kruskal算法是通过并查集，按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边,选其次。直到树中含有n - 1条边为止。
时间复杂度：O（E log E）（E为边数）
代码
#include <bits/stdc++.h>//万能头
using namespace std;
int fa[100001], a[100001], b[100001], s, p, n, k;
double ans;
struct node
{
double x, y, z;
}stu[1000001];
bool cmp(node a, node b)//结构体从小到大排序
{
return a.z < b.z;
}
int find(int x)//并查集
{
if(x != fa[x])
{
fa[x] = find(fa[x]);
}
return fa[x];
}//查找
void unity(int x, int y)
{
int r1 = find(x);
int r2 = find(y);
fa[r1] = r2;
}//合并
int main()
{
scanf("%d %d", &s, &p);
for(int i = 1; i <= p; i++)
{
scanf("%d %d", &a[i], &b[i]);
for(int j = 1; j < i; j++)
{
n++;//存图(也就这个意思吧...)
stu[n].z = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));//计算长度(不懂得可以查一下勾股定理)
stu[n].x = i;
stu[n].y = j;
}
}
for(int i = 1; i <= p; i++)
{
fa[i] = i;//自己的父亲一开始等于自己本身
}
sort(stu + 1, stu + n + 1, cmp);//排序
for(int i = 1; i <= n; i++)
{
if(find(stu[i].x) != find(stu[i].y))//祖先不同
{
unity(stu[i].x, stu[i].y);//合并
ans = stu[i].z;//取最小值(排过序了)
k++;
if(k >= p - s)//满足每一对哨所之间有一条通话路径（直接的或者间接的）
{
printf("%.2lf", ans);
return 0;//退出
}
}
}
return 0;
}