最小生成树

问题 F: 修建道路 (roads)

时间限制: 1 Sec 内存限制: 128 MB
提交状态

题目描述

Farmer John 最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。

所有N(1≤N≤1000个农场（用1...N顺次编号）在地图上都表示为坐标为(Xi,Yi)的点(0≤Xi≤1000000,0≤Yi≤1000000），两个农场间道路的长度自然就是代表它们的点之间的距离。

现在 Farmer John 也告诉了你农场间原有的M(1≤M≤1000条路分别连接了哪两个农场，他希望你计算一下，为了使得所有农场连通，他所需建造道路的最小总长是多少。

输入

第 1行: 2个用空格隔开的整数：N和 M
第2...N+1 行：第i+1行为2个用空格隔开的整数：Xi，Yi
第N+2...N+M+1行：每行用2个以空格隔开的整数i、j描述了一条已有的道路，这条道路连接了农场i和农场j

输出

第1行：输出使所有农场连通所需建设道路的最小总长，保留2位小数，不必做任何额外的取整操作。为了避免精度误差，计算农场间距离及答案时，请使用64位实型变量。

样例输入 Copy

样例输出 Copy

4.00

提示

样例解释

FJ 一共有4个坐标分别为 (1,1),(3,1),(2,3),(4,3)的农场。农场1和农场4之间原本就有道路相连。
FJ 选择在农场1和农场2 间建一条长度为2.00的道路，在农场3和农场4间建一条长度为2.00的道路。这样，所建道路的总长为4.00，并且这是所有方案中道路总长最小的一种。

对于所有的数据，1≤N,M≤1000,0≤Xi，Yi≤1000000

#include<bits/stdc++.h> 
#include <math.h>
using namespace std;
typedef long long ll; 
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=5e5+10;
struct node{
    int x,y;
    double z;
}a[maxn];
double ans;
int n,m,len,p;
int x[maxn],y[maxn];
int fa[maxn];
bool cmp(node x,node y){
    return x.z<y.z;
} 
double di(int i,int j){
    double xx,yy;
    xx=(double)(x[i]-x[j]);
    yy=(double)(y[i]-y[j]);
    return sqrt(xx*xx+yy*yy);
}
int find(int h) 
{    
    return fa[h]==h?h:fa[h]=find(fa[h]); 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&x[i]);
        scanf("%d",&y[i]);
    } 
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            a[++len].x=i;
            a[len].y=j;
            a[len].z=di(i,j);
        }
    }
    sort(a+1,a+len+1,cmp);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    } 
    p=n;
    int s,t;
    for(int i=1;i<=m;i++){
        s=read();
        t=read();
        int diss=find(s);
        int dist=find(t);
        if(diss!=dist){
            p--;
            fa[dist]=diss;
        } 
    }
    for(int i=1;i<=len;i++){
        if(p==1){
            break;
        }
        int s=a[i].x;
        int t=a[i].y;
        int diss=find(s);
        int dist=find(t);
        if(diss!=dist){
            p--;
            fa[dist]=diss;
            ans+=a[i].z;
        }
    }
    printf("%.2lf",ans); 
}