​
题目描述
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 <(const node &a)const{
    return w<a.w;//注意排序顺序和结构体排序对象
}

}e[10101000];
void addedge(long long u,long long v,long long w){

e[++ecnt].u=u;
e[ecnt].v=v;
e[ecnt].w=w;

}
int getf(int x){

return x==f[x]?x:f[x]=getf(f[x]);

}
long long xx(int x,int ww){

return 1ll*(ax[x]-ax[ww])*(ax[x]-ax[ww])+1ll*(ay[x]-ay[ww])*(ay[x]-ay[ww]);//先不开方，不然比较难处理，在后文计算的时候会进行处理；

}
//1ll*指的是转成lang lang 类型，如果不加可能会结果超int变为负数；
int main(){

cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>ax[i]>>ay[i];
}
for(int i=1;i<n;i++){
    for(int j=i+1;j<=n;j++){
        addedge(i,j,xx(i,j));//注意循环内容，为了避免循环到同一个点；
    }
}
for(int j=1;j<=m;j++){

    int a,b;
    cin>>a>>b;
    addedge(a,b,0);//这里不建议直接cin>>e[i].u>>e[i].v>>e[i].w;因为这道题是个单向边，但是双向边直接输入无法处理，所以建议写addedge函数；
}
for(int i=1;i<=n;i++){
    f[i]=i;//所有点的爹都是自己
}
sort(e+1,e+1+ecnt);

int cnt=0;
double aas=0;

for(int i=1;i<=ecnt;i++){//ecnt是边得个数
    int u=getf(e[i].u);
    int v=getf(e[i].v);//两个点找爹
    if(u!=v){
        cnt++;//边数++
        aas+=sqrt(e[i].w);//这里开方处理，注意aas数据类型；
        f[u]=v;//统一爹
    }
    if(cnt==n-1){
        break;
    }
}

printf("%.2lf",aas);//注意题目输出格式

}
​