洛谷题单 <最小生成树> building roads

洛谷题单<最小生成树> 2



krukal 的应用 题目告诉原有M条边 即修改M次并查集；考察对kruskal并查集的理解。
代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010, M = 1010;
struct edge{
    int a, b;
    double c;
    bool operator<(const edge& w){
        return c < w.c;
    }
}edges[N*N];//完全图 边数位N^2级别

int n, m, p[N], cnt;
long long px[N], py[N];

double get_len(int i,int j){
    long long x = (ll)(px[i] - px[j]) * (px[i] - px[j]);
    long long y = (ll)(py[i] - py[j]) * (py[i] - py[j]);

    return sqrt(x + y);
} 

int find(int x){
    if(x != p[x]) return p[x] = find(p[x]);
    else return x;
}

double kruskal(int cnt){
    sort(edges, edges + cnt);
    double res = 0;
    for(int i = 0;i < cnt; i++){
        int a = edges[i].a, b = edges[i].b;
        double c = edges[i].c;
        int x = find(a), y = find(b);
        if(x != y){
            p[x] = y;
            res += c;
        }
    } 
    return res;
} 

int main(){
    cin >> n >> m;
    for(int i = 0; i <= n; i++) p[i] = i;
    for(int i = 1; i <= n; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        px[i] = a, py[i] = b;
    }
    for(int i = 0; i < m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        int x = find(a), y = find(b);
        if(x != y) p[x] = y;
    }
    int cnt = 0; 
    for(int i = 1; i <= n; i++){    //建立完全图的边 
        for(int j = i + 1; j <= n; j++){
            double z = get_len(i, j);
            edges[cnt ++] = {i, j, z};
        }
    }

    double ans = kruskal(cnt); // 传入参数 ：边数 

    printf("%.2f", ans);

    return 0;

}