44pts

P3366 【模板】最小生成树

North_encounter @ 2023-08-22 10:25:26

#include<bits/stdc++.h>
using namespace std;
int fa[1000001];
int n,q;
int ans;
struct student {
    int u,v,w;
} m[1140514];
int cnt=0;
inline void chu() {
    for(int i=1; i<=n; i++) {
        fa[i]=i;
    }
}
inline int find(int k) {
    if(fa[k]==k) return k;
    return fa[k]=find(fa[k]);
}
inline bool cmp(student a,student b) {
    return a.w<b.w;
}
inline void kruskal() {
    sort(m+1,m+q+1,cmp);
    for(int i=1; i<=q; i++) {
        if(find(m[i].u)==find(m[i].v)) continue;
        ans+=m[i].w;
        fa[m[i].v]=fa[m[i].u];
        if(++cnt>=n-1) {
            return;
        }
    }
    if(cnt<n-1) {
        ans=-1;
    }
    return;
}
int main() {
    cin>>n>>q;
    for(int i=1; i<=q; i++) {
        cin>>m[i].u>>m[i].v>>m[i].w;
    }
    chu();
    kruskal();
    if(ans==-1){
        cout<<"orz";
    }
    else {
    cout<<ans;
    }

return 0;
}

by Iniaugoty @ 2023-08-22 10:46:05

@yhliuhao 并查集合并写错了

fa[m[i].v]=fa[m[i].u];

改成

fa[find(m[i].v)] = find(m[i].u);

by North_encounter @ 2023-08-22 10:48:42

@gty314159 已解决,感谢


|