【c++图论】洛谷P2872 [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 个点的坐标为 (x_i,y_i)(xi​,yi​)，这 nn 个点编号为 11 到 nn。给定 mm 条边，第 ii 条边连接第 u_iui​ 个点和第 v_ivi​ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

* 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 行每行两个整数 x_i,y_ixi​,yi​ 代表第 ii 个点的坐标。 接下来 mm 行每行两个整数 u_i,v_iui​,vi​ 代表第 ii 条边连接第 u_iui​ 个点和第 v_ivi​ 个点。

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

4.00

说明/提示 数据规模与约定

对于 100\%100% 的整数，1 \le n,m \le 10001≤n,m≤1000，1 \le x_i,y_i \le 10^61≤xi​,yi​≤106，1 \le u_i,v_i \le n1≤ui​,vi​≤n。

说明

Translated by 一只书虫仔。

这道题有没有很熟悉↓

类似可见

具体做法 

#include
#include
#include
#include
#include
using namespace std;
int n,m;
long long f[10100101];
int ax[10100010];
int ay[10100010];
int ecnt=0;
struct node{
	long long u,v,w,next;
	bool operator n>>m;
	for(int i=1;i>ax[i]>>ay[i];
	}
	for(int i=1;i>b;
		addedge(a,b,0);//这里不建议直接cin>>e[i].u>>e[i].v>>e[i].w;因为这道题是个单向边，但是双向边直接输入无法处理，所以建议写addedge函数；
	}
	for(int i=1;i