WA90分求助
查看原帖
WA90分求助
725807
lizeyuannb楼主2022/8/30 12:46
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1005, M = 1e6 + 5;

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

struct edge {
    int u, v;
    double w;
}e[M];
bool cmp(edge p, edge q) {
    return p.w < q.w;
}

int n, m, cnt, res;
int fa[N], x[N], y[N];
bool g[N][N];

int find(int x) {
	if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}

void Kruscal() {
    double ans = 0;
    for(int i = 1; i <= cnt; i ++) {
        if(find(e[i].u) != find(e[i].v)) {
            merge(e[i].u, e[i].v);
            ans += e[i].w;
            res --;
        }
        if(res == 1) {
        	printf("%.2lf", ans);
        	return ;
		}
    }
}

int main() {
    cin >> n >> m;
    res = n;
    for(int i = 1; i <= n; i ++) {
        scanf("%d%d", &x[i], &y[i]);
        fa[i] = i;
	}
    for(int i = 1, u, v; i <= m; i ++) {
        scanf("%d%d", &u, &v);
        merge(u, v);
        g[u][v] = g[v][u] = 1;
        res --;
    }
    edge tmp;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j < i; j ++) {
            if(!g[i][j]) {
            	tmp.u = i; tmp.v = j; tmp.w = dis(x[i], y[i], x[j], y[j]);
                g[i][j] = g[j][i] = 1;
                e[++cnt] = tmp;
            }
        }
    }
    sort(e+1, e+1+cnt, cmp);
    Kruscal();
    return 0;
}

QAQ

2022/8/30 12:46
加载中...