P1547题解
查看原帖
P1547题解
1778414
DeepSeekR5楼主2025/6/14 23:00
#include <bits/stdc++.h>
using namespace std;

const int n = 2005;
int p[n], h[n];

void in(int n) {
    for (int i = 0; i < n; i++) {
        p[i] = i;
        h[i] = 1;
    }
}

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

void Union(int x, int y) {
    int rx = Find(x), ry = Find(y);
    if (rx != ry) {
        if (h[rx] < h[ry]) p[rx] = ry;
        else {
            p[ry] = rx;
            if (h[rx] == h[ry]) h[rx]++;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m), w(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        u[i]--;
        v[i]--; 
    }

    vector<int> idx(m);
    for (int i = 0; i < m; i++) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return w[i] < w[j];
    });

    in(n);

    int max_weight = 0;
    for (int i = 0; i < m; i++) {
        int j = idx[i];
        if (Find(u[j]) != Find(v[j])) { 
            Union(u[j], v[j]);
            max_weight = max(max_weight, w[j]);
        }
    }

    cout << max_weight << endl;
    return 0;
}



if (rx != ry) {
    if (h[rx] < h[ry]) p[rx] = ry;
    else {
        p[ry] = rx;
        if (h[rx] == h[ry]) h[rx]++;
    }
}

}

int main() { int n, m; cin >> n >> m; vector u(m), v(m), w(m); for (int i = 0; i < m; i++) { cin >> u[i] >> v[i] >> w[i]; u[i]--; v[i]--; }

vector<int> idx(m);
for (int i = 0; i < m; i++) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int i, int j) {
    return w[i] < w[j];
});

in(n);

int max_weight = 0;
for (int i = 0; i < m; i++) {
    int j = idx[i];
    if (Find(u[j]) != Find(v[j])) { 
        Union(u[j], v[j]);
        max_weight = max(max_weight, w[j]);
    }
}

cout << max_weight << endl;
return 0;

}

2025/6/14 23:00
加载中...