题目链接：
呃呃，最小生成树里确实没有类似的性质。但我们假设我们已经选出了n-1条边，现在就要考虑安装卫星电话了。安装卫星电话会使得一些边的权值变为0，就一定会进入最小生成树。假如某条边本来就在MST当中（且不是最大边权），那么最大边权不会被改变；如果这条边不在MST中，或者就是边权最大边，最大边权就会改变，而且是变为原来的次大边权。明白了这个也就是道水题了，但需要注意，边的数量，也就是开好数组！！！
1 #include2 #include 3 #include 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 }