[Usaco2007 Dec]Building Roads 修建道路

Farmer John 最近得到了一些新的农场。他希望修建一些道路，使所有农场都能通过已有道路或新建道路互相到达。目前，一些农场之间已经有道路相连。

共有 $N$ 个农场，依次编号为 $1$ 到 $N$ 。农场 $i$ 在地图上的坐标为 $(X_i,Y_i)$ ，连接两个农场的道路长度等于它们所对应坐标点之间的欧氏距离。

已知目前共有 $M$ 条道路。请计算为了使所有农场连通，至少需要新建多长的道路。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$ ，分别表示农场数量和已有道路数量。

接下来 $N$ 行，第 $i$ 行包含两个以空格分隔的整数 $X_i$ 和 $Y_i$ ，表示农场 $i$ 的坐标。

接下来 $M$ 行，每行包含两个以空格分隔的整数 $i$ 和 $j$ ，表示农场 $i$ 与农场 $j$ 之间已有一条道路。

输出一个实数，表示使所有农场连通所需新建道路的最小总长度，保留小数点后 $2$ 位，无须进行任何额外的取整操作。

为避免精度误差，计算农场之间的距离及答案时应使用 $64$ 位浮点数。

4.00

Farmer John 共有 $4$ 个农场，坐标分别为 $(1,1)$ 、 $(3,1)$ 、 $(2,3)$ 和 $(4,3)$ 。农场 $1$ 与农场 $4$ 之间已有道路相连。

本题为 USACO 2007 December 试题「Building Roads（修建道路）」，题面与测试数据整理自 BZOJ。

4.00