J12 例题-2 Alien 的通讯网

题目描述

$\text{Alien}$ 们由于通信的需要，需要在 $N$ 个城市之间建立通讯网络。 为了方便问题的描述，将每个城市抽象为一个平面上的点 $(X_i, Y_i)$ 。旧社会留下了一些仍可以使用的双向通讯线路，共 $M$ 条。 每一条线路的费用是这两个城市之间的欧几里德距离。 现在 $\text{Alien}$ 们委托你来做一个方案，在这些城市之间建立起双向的通讯线路，使得任意两个城市的通讯畅通，并且费用总和最小。

输入格式

第一行两个整数 $N, M$，意义如上。 接下来 $N$ 行，每行两个数 $X_i, Y_i$，表示一个点的坐标。 接下来 $M$ 行，每行两个数 $A_i, B_i$，表示已经存在的通讯线路。

输出格式

一行一个数 $Ret$，表示答案，精确到小数点后两位。

输入样例

4 1
1 1
3 1
2 3
4 3
1 4

输出样例

4.00

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$N,M \le 1000$，$X_i,Y_i\le 10^5$。