#8 #9 #10求调

P3366 【模板】最小生成树

Ci15876399260 @ 2024-12-01 10:28:28

#include<bits/stdc++.h>

using namespace std;

const int maxm = 1e4 + 5;

struct tu{
    int u , v , w;
};

int n , m;
tu a[maxm];
int ne[505];

int find(int x){ 
    if(ne[x] == x) return x;
    ne[x] = find(ne[x]);
    return ne[x];
}

void uon(int x , int y){
    ne[find(x)] = find(y);
}

void arr(){
    for(int i = 1 ; i <= n ; i++){
        ne[i] = i;
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        cin >> a[i].u >> a[i].v >> a[i].w;
    }
    auto f = [](tu x , tu y) -> bool {
        return x.w < y.w;
    };
    sort(a , a + m , f);
    arr();
    int nn = 0;
    int ans = 0;
    for(int i = 0 ; i < m ; i++){
        if(find(a[i].u) != find(a[i].v)){
            uon(a[i].u , a[i].v);
            nn++;
            ans += a[i].w;
        }
    }
    if(nn == n - 1) cout << ans << endl;
    else cout << "orz" << endl;
    return 0;
}

by wangruiqi36 @ 2024-12-01 10:34:31

数组开小了吧@Ci15876399260


by Ci15876399260 @ 2024-12-01 12:36:13

@wangruiqi36谢谢提醒,过了


|