# 题目

## Description

The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed $D$, which depends of the power of the transceivers. Higher power yields higher $D$ but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of $D$ is the same for every pair of outposts.

Your job is to determine the minimum $D$ required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

## Input

The first line of input contains $N$, the number of test cases. The first line of each test case contains $1 \leq S \leq 100$, the number of satellite channels, and $S\leq P \leq 500$ , the number of outposts. $P$ lines follow, giving the $(x,y)$ coordinates of each outpost in km (coordinates are integers between $0$ and $10,000$).

## Output

For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to $2$ decimal points.

# 题意

1、任意两个站点都可以联系（直接或者间接）；

2、使任意两站点的最大通信花费变得最小。

# 思路

2、如果$u$,$v$不在同一个连通分量中,那么加入 $(u,v)$ 一定是最优解。

1、在一张全联通图的最小生成树中，新增一条权为0的边，新增加的边则取代形成的环中的另外一条边形成新的最小生成树。

2、在一张全连通图中，若在其最小生成树中挑选 $S$ 个节点，在其两两间添加权为 $0$ 的边，则新生成的边必定可以取代生成的环中的 $S−1$ 个边构成新的最小生成树。选择 $S$ 个节点，得到的最小生成树由 $S-1$ 条权为 $0$ 的边构成，接下来将剩下的点加入最小生成树里，只需要添加 $(N-1)-(S-1)=N-S$ 条边。

3、在一张全连通图中，新增的一条边可以和任意一条边构成环。

# 总结

-------------本文结束感谢您的阅读-------------