kruskal生成树,10pts,求调,玄关
查看原帖
kruskal生成树,10pts,求调,玄关
1086062
MoraxNB楼主2024/7/23 10:58
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5 + 10;
double n, m, vis[N], ans, vis2[N], mu, mv, sn;

struct point {
    double x, y;
}ab[N];

struct edge {
    int u, v;
    double w;
}a[N];
int cnt;

bool cmp(edge x, edge y) {
    return x.w < y.w;
}

void addedge(int u, int v, int w) {
    a[++cnt].u = u;
    a[cnt].v = v;
    a[cnt].w = w;
}

struct DSU {
    int id, fa[N];
    void init(int x) {
        for (int i = 1; i <= x; i++) fa[i] = i;
    }
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void hb(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        else fa[x] = fy;
    }
};
DSU d;
int ccnt;
void kruskal() {
    sort(a + 1, a + 1 + cnt, cmp);
    for (int i = 1; i <= cnt; i++) {
        if (ccnt == n - m) sn = 1;
        int u = d.find(a[i].u), v = d.find(a[i].v);
        if (u == v) continue;
        else {
            d.hb(u, v);
            ccnt++;
            if (sn) {
                cout << fixed << setprecision(2) << a[i].w;
                return;
            }
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        ab[i].x = x, ab[i].y = y;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            addedge(i, j, sqrt((ab[i].x - ab[j].x) * (ab[i].x - ab[j].x) + (ab[i].y - ab[j].y) * (ab[i].y - ab[j].y)));
            //addedge(j, i, sqrt(abs(pow(ab[i].x, 2) - pow(ab[j].x, 2)) + abs(pow(ab[i].y, 2) - pow(ab[j].y, 2))));
        }
    }
    d.init(n);
    kruskal();
    return 0;
}
2024/7/23 10:58
加载中...