题意：
给定n个点， 要求修p-1条路使其连通， 但是现在有s个卫星， 每两个卫星可以免费构成连通（意思是不需要修路了）， 问修的路最长距离是多少。
分析：
s个卫星可以代替s-1条路， 所以只要求最小生成树， 排序后后去掉s-1条边， 最大那条就是答案。
#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<cstdio>#include<cmath>#include<cstdlib>#include<ctime>#include<queue>#include<set>#include<map>#include<stack>#include<bitset>#include <iomanip>#define rep(i,a,b) for(int i = a; i < b; i++)#define _rep(i,a,b) for(int i = a; i <= b; i++)#define mem(a,n) memset(a,n,sizeof(a))#define fre(a) freopen(a,"r", stdin);typedef long long LL;using namespace std;const double inf = 1e9;int T,s,p;double p2p(double x1, double y1, double x2, double y2){ //距离可以需要时候再求出来 ???return sqrt((x1-x2) * (x1-x2) + (y1-y2)*(y1-y2));}double X[567], Y[567], dis[567];vector<int> G[567];bool vis[567];struct edge{ ???int u ,v; ???double d; ???edge(int _u,int ?_v, double _d):u(_u),v(_v),d (_d){};};bool cmp(edge a, edge b){ ???return a.d > b.d;}void prim(){ ???fill(dis, dis+567, inf); ???mem(vis,0); ???vis[1] = 1; ???dis[1] = 0; ???for(int i = 0; i < G[1].size(); i++){ ???????int v = G[1][i]; ???????dis[v] = p2p(X[1], Y[1], X[v], Y[v]); ???} ???vector<double> ans; ???set<int> in; ???rep(times, 0, p-1){ ???????double min_dis = 1e9; ???????int pick = -1; ???????_rep(i,1,p){ ???????????if(!vis[i] && dis[i] < min_dis){ ???????????????min_dis = dis[i], pick = i; ???????????} ???????} ???????vis[pick] = 1; ???????ans.push_back(min_dis);// ???????printf("min_dis : %.4f\n", min_dis); ???????rep(i,0,G[pick].size()){ ???????????int v = G[pick][i]; ???????????double d = p2p(X[pick], Y[pick], X[v], Y[v]); ???????????if(dis[v] > d) dis[v] = d; ???????} ???} ???sort(ans.begin(), ans.end()); ???if(s < 2){//如果小于2， 那么不能减少任意一条边 ???????printf("%.2f\n", ans[ans.size() - 1]); ???????return; ???} ???if(p - s - 1 >= ans.size()) { //如果s - 1多于边的总数， 那么不用任何一条边 ???????puts("0"); ???} ???else printf("%.2f\n", ans[p-s-1]); //找出第s-1大的边}int main(){ ???cin >> T; ???while(T--){ ???????cin >> s >> p; ???????_rep(i,1,p){ ???????????double x, y; ???????????cin >> x >> y; ???????????X[i] = x, Y[i] = y; ???????} ???????_rep(i,1,p)_rep(j,i+1,p){ //建一个完全图， 因为任意两点都是可达的 ???????????G[i].push_back(j); ???????????G[j].push_back(i); ???????} ???????prim(); ???????_rep(i,1,p) G[i].clear(); ???????mem(vis,0); ???????mem(X,0); ???????mem(Y,0); ???} ???return 0;}POJ 2349 Arctic Network（贪心 最小生成树）
原文地址：https://www.cnblogs.com/Jadon97/p/8325494.html