题解 P1991 【无线通讯网】
constructor
2018-10-04 17:23:34
这一题其实是一题很有意思的大综合题，尽管算法过程很简单，但是思考起来还是有难度的，由于题解中大部分的原理没有说出或者不完善，我就写一篇题解吧。
先看题面，由
>他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。
>收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。
可以发现这是一题求[瓶颈生成树](https://baike.baidu.com/item/%E7%93%B6%E9%A2%88%E7%94%9F%E6%88%90%E6%A0%91/2397900)的题目。
稍微解释一下，瓶颈生成树指的是在一个图$(E,V)$中一个$T \in E$使得$card(T) = G - 1 $且$T.max$是最小的。
定理： 瓶颈生成树和最小生成树的关系是最小生成树是瓶颈生成树的充分不必要条件。
这里可以使用[图拟阵](https://en.wikipedia.org/wiki/Matroid)进行证明，但是拟阵过于复杂，我不想在这里引入，你只需要脑补一遍kruskal算法的过程就应该知道这是对的了。
选用最小生成树的原因有两个：
- 最小生成树方便在图发生变化时维护其性质。
- 我也不会别的算法求瓶颈生成树了。
所以我们可以先求一个最小生成树，其中的最大边就是没有所谓的“卫星电话”时的答案了。
那么接下来怎么做呢？ 卫星电话的影响究竟是什么？其他题解中大部分说了一些类似于“联通块”“删边”的东西，引起了大规模的争论，但为什么答案是正确的呢？
事实上，边从来没有被删除过，而且也没有新的联通块出现。（但仍然不排除有方便思考的可能）。
那到底该怎么想？
注意一件事：
## 由于距离是客观存在的，所以本题中的图为完全图。
这个发现将不断伴随接下来的过程，是非常重要的性质。
好，已经扯了这么多废话了，那么不如再扯一点吧：
古人云：
>一生二，二生三，三生天下。
这是很有道理的。
- 一表达事物的本身，在此处对于一个“卫星电话”点来说，它到其他卫星电话点的距离为0，而不是边被删除了。
- 二表达事物内部的联系，在本题中，一对卫星电话点的距离为0
- 三表达事物和外部的联系，这点比较复杂我们稍后介绍。
当一个卫星电话出现时，没有什么表现，跳过。
当一对卫星电话出现时，分两种情况
- 没有无边的情况，因为本图是完全图
- 若这一对点之间边为树边，则他们的边权为0后若其为树上最大边，则答案变为树上第二大边，否则不变。
- 若这一对点之间为非树边：
那么**交换**两点之间路径的最大边（a. k. a. 边交换）(一样，自己脑补kruskal吧)。因为保证0距离是最小距离。
那么这是否说明可以随时移除当前最大的边吗？
那还得看引入新的点是否有影响。
当第三个点出现时，如：
那么会不会由于多对点产生其他影响呢？
首先前两个点交换了一条边，假定是标为虚线的这一条：
那么可以发现新得到的生成树是实线标识的这一条“M”形的折线。
这个时候我们尝试用新点对其他两点连边：
咦？图2中两点路径只比图1多包含了一条0权边！
是巧合吗？显然不是。这是因为当0权边产生时两边的卫星电话点早已连在一起，所以向他们进行连边时所能产生的出入只有一条或一些0权边而已！
那么我们可以把这样一组卫星点缩在一起，构成“卫星电话组”，即：
这样，我们就能通过连接组内组外任意两点，将一条路径上的最大边用0边更换掉。
很明显就知道这样一共能进行$(S-1)$次。那么我们就能够通过连接在生成树上尽量远的两点达到不断将生成树中的最大边更换掉的目的。
综上，生成树中前$[P-1 - (S-1)]$条边(i.e., P-S)中的最大边就是答案！
为了凑个题解的样子，下面还是给出我的C++11代码，但是建议代码还是~~抄~~借鉴别人的，我的代码可能比较小众。
```cpp
#include <iostream>
#include <list>
#include <algorithm>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <vector>
#include <numeric>
#ifdef DEBUG
#include <sstream>
std::stringstream stin(R"__(2 4
0 100
0 300
0 600
150 750
)__");
#else
#define stin std::cin
#endif // DEBUG
using edge = std::tuple<double, int, int>;
constexpr int maxn = 505;
int S, P;
std::vector<edge> gra, tree;
int p[maxn];
std::pair<double, double> pos[maxn];
constexpr double EuclidDistance(std::pair<int, int> p1, std::pair<int, int> p2)
{
return std::sqrt((p1.first - p2.first)*(p1.first - p2.first)+(p1.second - p2.second)*(p1.second - p2.second));
}
int find(int pos)
{
return p[pos] == pos ? pos : p[pos] = find(p[pos]);
}
int main()
{
stin >> S >> P;
for(int i = 1; i <= P; i++)
stin >> pos[i].first >> pos[i].second;
std::iota(p+1, p+1+P, 1);
for(int i = 1; i <= P - 1; i++)
for(int j = i+1; j <= P; j++)
{
auto dis = EuclidDistance(pos[i], pos[j]);
gra.emplace_back(dis, i, j);
gra.emplace_back(dis, j, i);
}
std::sort(gra.begin(), gra.end());
int count = 0;
for(auto& i : gra)
{
if(find(std::get<1>(i))!=find(std::get<2>(i)))
{
p[p[std::get<1>(i)]] = p[std::get<2>(i)];
count++;
}
if(count == P - S)
{
std::cout << std::fixed << std::setprecision(2) << std::get<0>(i) << std::ends;
return 0;
}
}
}
```