求最小生成树有两种常见的算法：Prim\text{Prim}Prim 和 Kruskal\text{Kruskal}Kruskal。 稠密图上前者快，否则后者快。 显然这道题不是稠密图，所以我使用了 Kruskal\text{Kruskal}Kruskal。 其实是我太蒻了，不会Prim Kruskal\text{Kruskal}Kruskal 的基本思想是贪心，对所有的边按边权进行排序，逐个判断，如果边的两端在新图中不连通，则将边加入新图。 通常使用并查集维护点的连通性。 基于并查集的 Kruskal\text{Kruskal}Kruskal 算法如下。

并查集+kruskal

使用了Kruskal 算法

//Kruskal最小生成树 #include<bits/stdc++.h> using namespace std; const int maxn=2e6+5; int fa[maxn],n,m; int _find(int x){ return fa[x]==x?x:fa[x]=_find(fa[x]); } void _union(int x,int y){ int fx=_find(x),fy=_find(y); if(fx=fy){ return; } fa[fx]=fy; } struct edge{ int u,v,val; }e[maxn]; bool cmp(edge x,edge y){ return x.val<y.val; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ cin>>e[i].u>>e[i].v>>e[i].val; } //关键步骤1：将所有边按权值从小到大排序 sort(e+1,e+m+1,cmp); int ans=0,cnt=0;//ans:最小生成树的总权值，cnt:已选边的数量 //关键步骤2：遍历所有边 for(int i=1;i<=m;i++){ int u=e[i].u,v=e[i].v;//如果边的两个端点已在同一个连通分量 ，跳过 if(_find(u)=_find(v)) continue; _union(u,v);//合并两个端点所在连通分量 ans+=e[i].val,cnt++; } //判断是否形成生成树：边数应为节点-1； if(cnt!=n-1) cout<<"orz"<<endl;//图不连通 else cout<<ans<<endl;//输出最小生成树权值和 }

是题解,也许吧.

#include<bits/stdc++.h> using namespace std; const int N=2e5+9; int f[N],n,m,ans,cnt; struct node{ int x,y,z; }a[N]; bool cmp(node n,node m){ return n.z<m.z; } int find(int x){ if(f[x]x){ return x; } return f[x]=find(f[x]); } void merge(int x,int y){ x=find(x); y=find(y); f[x]=y; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ f[i]=i; } for(int i=1;i<=m;i++){ cin>>a[i].x>>a[i].y>>a[i].z; } sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++){ if(find(a[i].x)!=find(a[i].y)){ merge(a[i].x,a[i].y); cnt++; ans+=a[i].z; } } if(cntn-1)cout<<ans; else cout<<"orz"; return 0; }