最小生成树模板（prim,heap-prim,kruskal）

prim

出圈法，时间复杂度$O(n^2)$

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 5000
#define inf 100000000
struct edge{int v,w;
};
vector<edge>e[MAX_N+5];
int d[MAX_N+5],vis[MAX_N+5];
int n,m;
int ans=0,cnt=0;
bool prim(int s)
{for(int i=0;i<=n;i++)d[i]=inf;d[s]=0;for(int i=1;i<=n;i++){int u=0;for(int j=1;j<=n;j++)if(!vis[j]&&d[j]<d[u])u=j;vis[u]=1;ans+=d[u];if(d[u]!=inf)cnt++;for(auto ed:e[u]){int v=ed.v,w=ed.w;if(d[v]>w)d[v]=w;}}return n==cnt;
}
int main()
{cin>>n>>m;for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[a].push_back({b,c});e[b].push_back({a,c});}if(!prim(1)){cout<<"orz"<<endl;return 0;}else{cout<<ans<<endl;return 0;}return 0;} 

heap-prim

出队法，时间复杂度$O(mlogm)$

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX_N 5000
#define inf 100000000
struct edge{int v,w;
};
vector<edge>e[MAX_N+5];
int d[MAX_N+5],vis[MAX_N+5];
int n,m;
int ans=0,cnt=0;
priority_queue<pair<int,int>>q;
bool prim(int s)
{for(int i=0;i<=n;i++)d[i]=inf;d[s]=0;q.push({0,s});while(!q.empty()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;ans+=d[u];cnt++;for(auto ed:e[u]){int v=ed.v,w=ed.w;if(d[v]>w){d[v]=w;q.push({-d[v],v});}}}return n==cnt;
}
int main()
{cin>>n>>m;for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[a].push_back({b,c});e[b].push_back({a,c});}if(!prim(1)){cout<<"orz"<<endl;return 0;}else{cout<<ans<<endl;return 0;}return 0;} 

kruskal

加边法，时间复杂度$O(mlogm)$

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 5000
#define MAX_M 200000
#define inf 100000000
struct edge{int u,v,w;bool operator<(const edge&t){return w<t.w;}
}e[MAX_M+5];
int k=0;
int n,m;
int fa[MAX_N+5],ans,cnt;
int find(int x)
{return fa[x]==x?x:find(fa[x]);
}
bool kruskal(){sort(e+1,e+m+1);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){int x=find(e[i].u);int y=find(e[i].v);if(x!=y){fa[x]=y;ans+=e[i].w;cnt++;}}return cnt==n-1;
}
int main()
{cin>>n>>m;for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[++k]={a,b,c};}if(!kruskal()){cout<<"orz"<<endl;return 0;}else{cout<<ans<<endl;return 0;}return 0;}