#P2872. [USACO07DEC] Building Roads S

[USACO07DEC] Building Roads S

题目描述

Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

给定 nn 个点的坐标,第 ii 个点的坐标为 (xi,yi)(x_i,y_i),这 nn 个点编号为 11nn。给定 mm 条边,第 ii 条边连接第 uiu_i 个点和第 viv_i 个点。现在要求你添加一些边,并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Two space-separated integers: Xi and Yi

* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

第一行两个整数 n,mn,m 代表点数与边数。
接下来 nn 行每行两个整数 xi,yix_i,y_i 代表第 ii 个点的坐标。
接下来 mm 行每行两个整数 ui,viu_i,v_i 代表第 ii 条边连接第 uiu_i 个点和第 viv_i 个点。

输出格式

* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

一行一个实数代表添加的边的最小长度,要求保留两位小数,为了避免误差, 请用 6464 位实型变量进行计算。

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

提示

数据规模与约定

对于 100%100\% 的整数,1n,m10001 \le n,m \le 10001xi,yi1061 \le x_i,y_i \le 10^61ui,vin1 \le u_i,v_i \le n

说明

Translated by 一只书虫仔。