题目链接：https://www.luogu.org/problemnew/show/P1991
呃呃，最小生成树里确实没有类似的性质。但我们假设我们已经选出了n-1条边，现在就要考虑安装卫星电话了。安装卫星电话会使得一些边的权值变为0，就一定会进入最小生成树。假如某条边本来就在MST当中（且不是最大边权），那么最大边权不会被改变；如果这条边不在MST中，或者就是边权最大边，最大边权就会改变，而且是变为原来的次大边权。明白了这个也就是道水题了，但需要注意，边的数量，也就是开好数组！！！
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 5 using namespace std; 6 7 const int maxn = 505; 8 9 int x[maxn], y[maxn]; 10 11 struct Edge { 12 int u, v; 13 double w; 14 bool operator < (const Edge& rhs) const { 15 return w < rhs.w; 16 } 17 } edge[maxn * maxn / 2]; 18 19 inline int pw2(int x) { 20 return x * x; 21 } 22 23 inline double dis(int i, int j) { 24 return sqrt(pw2(x[i] - x[j]) + pw2(y[i] - y[j])); 25 } 26 27 int fa[maxn]; 28 29 int dj_find(int i) { 30 if (i == fa[i]) return i; 31 else return fa[i] = dj_find(fa[i]); 32 } 33 34 inline void dj_merge(int a, int b) { 35 fa[dj_find(a)] = dj_find(b); 36 } 37 38 int main() { 39 int s, p, eid = 0, cnt = 0; 40 scanf("%d%d", &s, &p); 41 for (int i = 1; i <= p; ++i) 42 scanf("%d%d", &x[i], &y[i]); 43 for (int i = 1; i < p; ++i) 44 for (int j = i + 1; j <= p; ++j) 45 edge[++eid].u = i, edge[eid]. v = j, edge[eid].w = dis(i, j); 46 sort(edge + 1, edge + eid + 1); 47 for (int i = 1; i <= p; ++i) fa[i] = i; 48 for (int i = 1; i <= eid; ++i) { 49 int u = edge[i].u, v = edge[i].v; 50 if (dj_find(u) != dj_find(v)) { 51 dj_merge(u, v); 52 if (++cnt == p - s) { 53 printf("%.2f", edge[i].w); 54 return 0; 55 } 56 } 57 } 58 return 0; 59 }