首页 > 基站
开通博客写题解
头像 Muscari
发表于 2020-10-02 21:36:10
如果每个点都是基站，问题即求完全图最小生成树的最大边。 那么如果去掉原图中不是基站的点，即建一个新图，两个基站连一条边权为最短路的边，题目就变成上面的情况了。 因此可以考虑优化这个连边。设 表示离 最近的基站，跑多源最短路即可求出。那么对于一条边 ，如果 ，则在 和 间连一条边权为 的边 展开全文
去ta的博客 赞 (6) 回复(3) 收起
头像 Dear㉿You
发表于 2020-10-13 13:38:51
基站 前言 终于把这道题补上了 心路 当时画了个这样的图当时想着能否找出这些红点之间的距离。但似乎不太好实现。换一种思路，因为题目要求最小的d中的最大值。通过图发现点 3 在点 1 与点 6 之间，可以通过3过渡。过渡——对于一个点来说，一定会有离他最近的一个红点，而对于一条边上的两个点，他们 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 EternalEpic
发表于 2020-10-03 22:53:24
建出MST即可，但先要用dijkstra求出每个点到达的最近基站。可预先将所有基站放入堆中迭代。 // Program written by Liu Zhaozhou ~~~ #include <bits/stdc++.h> #include <tr1/unordered_map& 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”