P3366 【模板】最小生成树——题解

解题思路

使用 Kruskal 算法。把所有边按权值从小到大排序，依次检查：若一条边的两个端点当前属于不同连通块，就选入生成树并用并查集合并。选到 $N-1$ 条边后得到最小生成树；若最终不足 $N-1$ 条，说明原图不连通。

复杂度分析

排序耗时 $O(M\log M)$，并查集操作近似 $O(M\alphalpha(N))$，空间复杂度 $O(N+M)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
struct Edge{int u,v,w;};
int fa[5005];
int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,m; cin>>n>>m;
    vector<Edge> e(m);
    for(auto &x:e) cin>>x.u>>x.v>>x.w;
    sort(e.begin(),e.end(),[](const Edge&a,const Edge&b){return a.w<b.w;});
    for(int i=1;i<=n;i++) fa[i]=i;
    long long ans=0; int cnt=0;
    for(auto x:e){
        int a=findf(x.u),b=findf(x.v);
        if(a!=b){fa[a]=b; ans+=x.w; cnt++; if(cnt==n-1) break;}
    }
    if(cnt==n-1) cout<<ans<<'\n'; else cout<<"orz\n";
    return 0;
}

#include <bits/stdc++.h> using namespace std; struct Edge{int u,v,w;}; int fa[5005]; int findf(int x){return fa[x]x?x:fa[x]=findf(fa[x]);} int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin>>n>>m; vector e(m); for(auto &x:e) cin>>x.u>>x.v>>x.w; sort(e.begin(),e.end(),[](const Edge&a,const Edge&b){return a.w<b.w;}); for(int i=1;i<=n;i++) fa[i]=i; long long ans=0; int cnt=0; for(auto x:e){ int a=findf(x.u),b=findf(x.v); if(a!=b){fa[a]=b; ans+=x.w; cnt++; if(cntn-1) break;} } if(cnt==n-1) cout<<ans<<'\n'; else cout<<"orz\n"; return 0; }