F - Building Roads S

Description

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)(xi​,yi​)，这 nn 个点编号为 11 到 nn。给定 mm 条边，第 ii 条边连接第 uiui​ 个点和第 vivi​ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

Input

* 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,yixi​,yi​ 代表第 ii 个点的坐标。
接下来 mm 行每行两个整数 ui,viui​,vi​ 代表第 ii 条边连接第 uiui​ 个点和第 vivi​ 个点。

Output

* 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 位实型变量进行计算。

Sample 1

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

4.00

Hint

数据规模与约定

对于 100%100% 的整数，1≤n,m≤10001≤n,m≤1000，1≤xi,yi≤1061≤xi​,yi​≤106，1≤ui,vi≤n1≤ui​,vi​≤n。

说明

Translated by 一只书虫仔。

最小生成树，但要注意要加上m中已经为树的边数

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
int n, m, ll = 0,v,u,ss=0;
double min = 0.00;
int b[1001];
struct pppp {
	int x, y;
}bb[1001];
struct s {
	int x, y;
	double k;
};
struct s a[1000001], d[1000001];
//归并排序将其从小到打排序
void digui(int i, int j) {
	if (i >= j) {
		return;
	}
	int mid = i + (j - i) / 2;
	digui(i, mid);
	digui(mid + 1, j);
	int r = i, l = mid + 1, h = i;
	while (r <= mid && l <= j) {
		if (a[r].k < a[l].k) {
			d[h].k = a[r].k;
			d[h].x = a[r].x;
			d[h].y = a[r].y;
			h++;
			r++;
		}
		else {
			d[h].k = a[l].k;
			d[h].x = a[l].x;
			d[h].y = a[l].y;
			h++;
			l++;
		}
	}
	while (r <= mid) {
		d[h].k = a[r].k;
		d[h].x = a[r].x;
		d[h].y = a[r].y;
		h++;
		r++;
	}
	while (l <= j) {
		d[h].k = a[l].k;
		d[h].x = a[l].x;
		d[h].y = a[l].y;
		h++;
		l++;
	}
	h = i;
	while (h <= j) {
		a[h].k = d[h].k;
		a[h].x = d[h].x;
		a[h].y = d[h].y;
		h++;
	}
}
//并查集
int cha(int i) {
	if (b[i] != i) {
		return b[i]= cha(b[i]);
	}
	else {
		return b[i];
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1;i <= n;i++) {
		b[i] = i;
	}
	for (int i = 1;i <= n;i++) {
		scanf("%d %d", &bb[i].x, &bb[i].y);
	}
	for (int i = 1;i <= m;i++) {
		scanf("%d %d", &u, &v);
		if (b[cha(u)] == b[cha(v)])//可能有已经是同一个合集相连
			ss++;
		b[cha(u)] = b[cha(v)];
	}
	int e = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = i + 1;j <= n;j++) {
			a[e].x = i;
			a[e].y = j;
			a[e].k = (double)(sqrt((double)pow(bb[i].x - bb[j].x,2)  + (double)pow(bb[i].y - bb[j].y,2)));
			e++;
		}
	}
	digui(0, e - 1);
	int i = 0;
	while (ll <n-m-1+ss&&i<e) {
		if (cha(a[i].x) != cha(a[i].y)) {
			min += a[i].k;
			b[cha(a[i].y)] = b[cha(a[i].x)];
			ll++;
		}
		i++;
	}
	printf("%.2lf\n", min);
	return 0;
}