首页 > 代码库 > （最小生成树/最小瓶颈生成树） 2017武汉现场赛 - Wifi Relay
（最小生成树/最小瓶颈生成树） 2017武汉现场赛 - Wifi Relay
题意：
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\n", prim());56 57 }58 59 return 0;60 61 }
（最小生成树/最小瓶颈生成树） 2017武汉现场赛 - Wifi Relay
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。