洛谷 P2872 [USACO07DEC]道路建设Building Roads

时间：2022-01-02 03:18:55

题目描述

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个点的坐标,其中一些点已经连通,现在要把所有点连通,求修路的最小长度.

输入输出格式

输入格式：

  • 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.

输出格式：

  • 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.

输入输出样例

输入样例#1： 
4 1

1 1

3 1

2 3

4 3

1 4
输出样例#1： 
4.00
 
 

裸kruskal

屠龙宝刀点击就送

#include <algorithm>

#include <cstdio>

#include <cmath>

#define N 1000005

typedef long long LL;

using namespace std;

int    cnt,fa[],n,m,q;

LL x[],y[];

struct Edge

{

    int x,y;

    double dist;

    bool operator<(Edge a)const

    {

        return dist<a.dist;

    }

}edge[N];

int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);}

double calc(LL x1,LL y1,LL x2,LL y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;++i)

    {

        fa[i]=i;

        scanf("%lld%lld",&x[i],&y[i]);

    }

    for(int u,v,i=;i<=m;++i)

    {

        scanf("%d%d",&u,&v);

        fa[find_(v)]=find_(u);

    }

    for(int i=;i<=n;++i)

     for(int j=i+;j<=n;++j)

      edge[++cnt]=(Edge){i,j,calc(x[i],y[i],x[j],y[j])};

    sort(edge+,edge++cnt);

    double sum=;

    for(int num=,i=;i<=cnt;++i)

    {

        int fx=find_(edge[i].x),fy=find_(edge[i].y);

        if(fx!=fy)

        {

            fa[fy]=fx;

            sum+=edge[i].dist;

            if(++num==n-) break;

        }

    }

    printf("%.2lf",sum);

    return ;

}

相关文章