题意：所有哨所 都要配备无线电收发器，每两个配备了卫星电话的哨所无论距离多远都可以通话。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。 收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。你的任务是 确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。
用 kruskal 求图的最小生成树，卫星电话的作用就是 把最小生成树里的边从大到小一条条的去掉，剩下的最大的那一条就是题目要求的 D。
求图的最小生成树：因为每两个哨所的通话路径都是直接或 间接 连通的，且题目要求两个哨所之间的最大通话距离尽可能小。
假设只有一台卫星电话，该哨所不能通过卫星电话与其他哨所进行通话，所以答案就是最小生成树里面最大的边。
假设有两台卫星电话，这两台卫星电话肯定是安装在连接最小生成树里面最大的边的两个哨所上，因此答案是最小生成树里面倒数第二大的边。
假设有三台卫星电话，其中两台卫星电话安装在连接最小生成树里面最大的边的两个哨所上，另一台安装在最小生成树里面倒数第二大的那条边上的远离其他两台卫星电话的那个哨所上。
三个哨所示例如下图：其中两个卫星电话装在哨所 1 和 哨所 2，然后另一个装在哨所 5，这样哨所 5 想要和哨所 6 通信可以通过无线电收发器，一开始就是忽略了（ 所有哨所 都要配备无线电收发器）。哨所 5 想要和哨所 4 通信可以通过卫星电话与哨所 1 通信，再从哨所 1 通过无线电收发器与哨所 3 通信，然后再与哨所 4 通信（通话路径可以是 间接 的）。 如果是四个卫星电话，假设第三大的边是在哨所 8 和 哨所 9 之间的那一条边，我们可以把卫星电话安装在哨所 9， 这样子就可以把这第三大的边去掉了。
总结：有 n 个卫星电话就可以从最小生成树里去掉最大的 n - 1 条边。
洛谷 P1991 无线运输网
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayDeque; import java.util.PriorityQueue; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(br); static int nextInt() throws IOException { st.nextToken(); return (int)st.nval; } public static void main(String[] args) throws IOException { int s = nextInt(); // 可安装的卫星电话的哨所数 int p = nextInt(); // 边防哨所的数量 int[][] arr = new int[p][2]; // 边防哨所的坐标 PriorityQueue<Edge> pq = new PriorityQueue<>(); for (int i = 0; i < p; i++) { arr[i][0] = nextInt(); arr[i][1] = nextInt(); } // 求出每两个哨所之间的距离加入图中 for (int i = 0; i < p; i++) { for (int j = i + 1; j < p; j++) { double weight = Math.sqrt(Math.pow(arr[i][0] - arr[j][0], 2) + Math.pow(arr[i][1] - arr[j][1], 2)); Edge e = new Edge(i, j, weight); pq.add(e); } } Kruskal kru = new Kruskal(p, pq); Edge ans = null; for (int i = 1; i <= p - s; i++) { ans = kru.queue.poll(); } System.out.printf("%.2f\n", ans.weight); } } class Edge implements Comparable<Edge> { int v; int w; double weight; public Edge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; } // 返回边的其中一个顶点 int either() { return v; } // 返回与v不同的另一个顶点 int other(int v) { if (v == this.w) { return this.v; } return this.w; } @Override public int compareTo(Edge o) { return Double.compare(this.weight, o.weight); } } class UnionFind { int[] parent; int[] size; // 根结点对应的分量的大小 int count; // 连通分量的数量 public UnionFind(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } for (int i = 0; i < n; i++) { size[i] = 1; } count = n; } int find(int p) { while (parent[p] != p) { p = parent[p]; } return p; } boolean isConnected(int p, int q) { return find(p) == find(q); } void union(int p, int q) { int pRoot = find(p); int qRoot = find(q); if (pRoot == qRoot) { return; } // 让小的指向大的 if (size[pRoot] < size[qRoot]) { parent[pRoot] = qRoot; size[qRoot] += size[pRoot]; } else { parent[qRoot] = pRoot; size[pRoot] += size[qRoot]; } count--; } } class Kruskal { ArrayDeque<Edge> queue; // 存放最小生成树中的边 PriorityQueue<Edge> pq; int ver; // 顶点数 public Kruskal(int ver, PriorityQueue<Edge> pq) { queue = new ArrayDeque<Edge>(); this.ver = ver; this.pq = pq; UnionFind uf = new UnionFind(ver); while (! pq.isEmpty() && queue.size() < ver - 1) { Edge e = pq.poll(); int v = e.either(); int w = e.other(v); if (uf.isConnected(v, w)) { continue; } uf.union(v, w); queue.add(e); } } }