题目
https://www.luogu.com.cn/problem/P1991
分析
本题使用kruskal算法，再能保证所有的节点都能够被连接的情况下，将构成最小生成树的边的长度入队进行排列，除去可以使用卫星电话的节点（就是除去排在前面最长的边）输出最长的边
至于添加边的话，要添加不同节点之间的距离，而且A B 、B A只添加一次就行
代码
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<vector> using namespace std; #define maxm 1000001 #define maxn 1010 struct node { int from; int to; double dis; }e[maxm * 2];//自己补的边 struct point { double x; double y; }list[maxn];//点集 bool cmp(struct node &a, struct node &b) { return a.dis < b.dis; } bool cmp2 (struct node &a, struct node &b) { return a.dis > b.dis; } vector<node> qq; int father[maxn]; int s,p, cnt = 0; double allcount = 0;//答案 int find(int x) { if (father[x] == x) return x; return father[x] = find(father[x]); } int kruskal() { sort(e, e + cnt, cmp); for (int i = 0; i < cnt; i++) { int tempx = find(e[i].from); int tempy = find(e[i].to); if (tempx == tempy)continue; qq.push_back(e[i]); father[tempx] = tempy; } return allcount; } int main() { scanf("%d%d", &s, &p); for (int i = 1; i <= p; i++) scanf("%lf%lf", &list[i].x, &list[i].y); for (int i = 1; i <= p; i++)father[i] = i; for (int i = 1; i <= p; i++) { for (int j = 1; j <= i; j++)//这里只需要补一半的边 1 2 300 ； 2 1 300 对本题意义一样 { if (i == j)continue; e[cnt].from = j; e[cnt].to = i; e[cnt].dis = sqrt((list[i].x - list[j].x)*(list[i].x - list[j].x) + (list[i].y - list[j].y)*(list[i].y - list[j].y)); cnt++; } } kruskal(); sort(qq.begin(), qq.end(), cmp2); double ans = qq[s-1].dis; printf("%.2lf",ans ); }