最小生成树 常见算法为：Prim和Kruskal
Prim: 对节点进行处理，节点少边多的稠密图更优。 Kruskal: 对边进行处理，边少的图更优。
Luogu,P3366 【模板】最小生成树
Prim做法: 以某一结点为根,更新子节点,若更新成功,寻找其中长度最小的作为新节点. 朴素做法复杂度:O(n2) 寻找其中长度最小的可用堆优化.
#include<bits/stdc++.h> #define INF 1e9 #define MAXN 5005 using namespace std; struct Prim { struct To { int id; int v; }; struct Node { list<To>to; int used; }; Node node[MAXN]; queue<int>q; int mindis[MAXN];//点i到生成树的最小边权值 int n; void init(int n){ for(int i=1;i<=n;i++)mindis[i]=INF; this->n=n; } void add(int u,int v,int w){ node[u].to.push_back({v,w}); } void prim(int root){ q.push(root); mindis[root]=0; while(!q.empty()) { int now=q.front();q.pop(); node[now].used=1; int minid=-1,minv=1e9; for(auto& to:node[now].to){ if(node[to.id].used)continue; if(to.v<mindis[to.id]){ mindis[to.id]=to.v; } } for(int i=1;i<=n;i++){ if(!node[i].used){ if(mindis[i]<minv){ minv=mindis[i]; minid=i; } } } if(minid!=-1)q.push(minid); } } }; int n,m,x,y,z,ans=0; Prim a; int main() { cin>>n>>m; a.init(n); for(int i=1;i<=m;i++){ cin>>x>>y>>z; a.add(x,y,z); a.add(y,x,z); } a.prim(1); for(int i=1;i<=n;i++){ans+=a.mindis[i];} cout<<ans<<endl; return 0; }堆优化：
#include<bits/stdc++.h> #define MAXN 5005 #define INF 1e9 using namespace std; struct Prim { struct To { int id,v; bool operator<(const To&bb)const{ return v>bb.v; } }; struct Node { vector<To>to; }; Node node[MAXN]; int mindis[MAXN]; int vis[MAXN]; priority_queue<To>q; void init(int n){ for(int i=1;i<=n;i++){ mindis[i]=INF;vis[i]=0; node[i].to.clear(); } } void add(int x,int y,int v){ node[x].to.push_back({y,v}); } int prim(int n){ q.push({1,0});//root = 1; mindis[1]=0; int ret=0; while(!q.empty()) { auto now=q.top();q.pop(); if(vis[now.id])continue; vis[now.id]=1; ret+=now.v; for(auto& i:node[now.id].to){ if(!vis[i.id]){ mindis[i.id]=min(mindis[i.id],i.v); q.push({i.id,i.v}); } } } return ret; } }; int n,m,x,y,z,ans=0; Prim prim; int main() { cin>>n>>m; prim.init(n); for(int i=1;i<=m;i++){ cin>>x>>y>>z; prim.add(x,y,z); prim.add(y,x,z); } ans=prim.prim(n); cout<<ans<<"\n"; return 0; }Kruskal做法: (update 2.9) 将所有边入队,寻找最短边,连接其两边的节点为一棵树,若两节点已在同一棵树上,则跳过(判断是否在同一棵树可用并查集). 该方法比Prim更易理解和编写. 复杂度大概: O(mlogm)
#include<bits/stdc++.h> #define MAXN 200005 using namespace std; struct Kruskal { struct EDGE { int a,b,v; bool operator<(const EDGE& bb) const{ return v>bb.v; } }; static const int maxn=MAXN; int f[maxn]; //EDGE edge[maxn]; priority_queue<EDGE>q; void init(int n){ for(int i=1;i<=n;i++){f[i]=i;} while(!q.empty())q.pop(); } void addEdge(int x,int y,int v){ this->q.push({x,y,v}); } int find(int x){ if(f[x]==x)return x; return f[x]=find(f[x]); } int kruskal(int n){ int totedge=0,ret=0; while(!q.empty()) { EDGE now=q.top();q.pop(); int fa=find(now.a); int fb=find(now.b); if(fa!=fb){ totedge++; ret+=now.v; f[fa]=fb; } if(totedge>=n-1)break; } return ret; } }; int n,m,x,y,z,ans=0; Kruskal kru; int main() { cin>>n>>m; kru.init(n); for(int i=1;i<=m;i++){ cin>>x>>y>>z; kru.addEdge(x,y,z); } cout<<kru.kruskal(n); return 0; }