P2872 [USACO07DEC] Building Roads S

P2872 [USACO07DEC] Building Roads S

题目描述

给定 $n$ 个点的坐标，第 $i$ 个点的坐标为 $(x_i,y_i)$，这 $n$ 个点编号为 $1$ 到 $n$。给定 $m$ 条边，第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

第一行两个整数 $n,m$ 代表点数与边数。
接下来 $n$ 行每行两个整数 $x_i,y_i$ 代表第 $i$ 个点的坐标。
接下来 $m$ 行每行两个整数 $u_i,v_i$ 代表第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。

输出格式

一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差，请用 $64$ 位实型变量进行计算。

输入输出样例 #1

输入 #1

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

输出 #1

4.00

说明/提示

数据规模与约定

对于 $100\%$ 的整数，$1\le n,m\le 1000$，$1\le x_i,y_i\le 10^6$，$1\le u_i,v_i\le n$。

说明

Translated by 一只书虫仔。

其实还是求MST，只不过边变成了未联通的边。将已给出的边以权值0加入边数组中，跑一下最短路即可。

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int find_(vector<int> &p, int x){
    if(p[x] == x) return x;
    else {
        p[x] = find_(p, p[x]);
        return p[x];
    }
}
int main(){
    int n, m;
    cin>>n>>m;
    vector<pair<ll, ll>> p(n+1);
    for(int i = 1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
    }
    vector<tuple<long double, int, int>> e;
    for(int i = 0;i<m;i++){
        int u, v;
        cin>>u>>v;
        e.emplace_back(0.0, u, v);
    }
    for(int i = 1;i<n;i++){
        for(int j = i+1;j<=n;j++){
            e.emplace_back(sqrt((p[i].first-p[j].first)*(p[i].first-p[j].first) + (p[i].second-p[j].second)*(p[i].second-p[j].second)), i, j);
        }
    }
    sort(e.begin(), e.end());
    vector<int> pa(n+1);
    for(int i = 1;i<=n;i++){
        pa[i] = i;
    }
    double sum = 0;
    int cnt = 0;
    for(auto i : e){
        auto [w, u, v] = i;
        int r1 = find_(pa, u);
        int r2 = find_(pa, v);
        if(r1 != r2){
            pa[r1] = r2;
            sum+=w;
            cnt++;
        }
        if(cnt==n-1) break;
    }
    printf("%.2lf", sum);
    return 0;
}