（最小生成树/最小瓶颈生成树） 2017武汉现场赛
题意：
n个无线AP，有xy坐标属性，现在n个无线AP要桥接在一起不能断开连接，现在要求无线AP无线网络的覆盖半径最小是多少
分析：
看起来是像是最小生成树，这里是是求生成树中最长的边最短，就是最小瓶颈生成树。
可以证明最小瓶颈生成树就是最小生成树，详细看刘汝佳《算法入门经典训练指南》343页。
当时现场的时候，想试试最小生成树了，结果以为n方复杂度过不去，就没写，现在想起来，真是坑哦。
这题n有10000，所以不能直接建邻接矩阵，而是采用动态计算距离就行了。
比赛结束了随便一写就A了。。。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 6 using namespace std; 7 8 const int inf = 0x3f3f3f3f; 9 const int maxn = 10010; 10 11 double x[maxn]; 12 double y[maxn]; 13 14 int n; 15 16 double lowc[maxn]; 17 bool vis[maxn]; 18 19 double dis(double x1, double y1, double x2, double y2) { 20 return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)); 21 } 22 23 double prim() { 24 double res = 0; 25 memset(vis, 0, sizeof(vis)); 26 vis[0] = true; 27 for(int i = 1; i < n; i++)lowc[i] = dis(x[0], y[0], x[i], y[i]); 28 for(int i = 1; i < n; i++) { 29 double minc = inf; 30 int p = -1; 31 for(int j = 0; j < n; j++) { 32 if(!vis[j] && lowc[j] < minc) { 33 minc = lowc[j]; 34 p = j; 35 } 36 } 37 res = max(res, minc); 38 vis[p] = true; 39 for(int j = 0; j < n; j++) { 40 double d = dis(x[p], y[p], x[j], y[j]); 41 if(!vis[j] && lowc[j] > d) { 42 lowc[j] = d; 43 } 44 } 45 } 46 return res / 2; 47 } 48 49 50 int main() { 51 while(~scanf("%d", &n)) { 52 for(int i = 0; i < n; i++) { 53 scanf("%lf%lf", &x[i], &y[i]); 54 } 55 printf("%.9f ", prim()); 56 57 } 58 59 return 0; 60 61 }