最小生成树模板(prim，kruskal)

（一）最小生成树模板prim

//prim最小生成树,判断图连不连通 
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define For(a,b) for(int i=0;i<b;i++)
#define mem(x) memset(x,0,sizeof(x))
#define sf scanf
#define pf printf
#define maxn 3010
int gcd(int a,int b){ return b>0?gcd(b,a%b):a;}
typedef long long ll;
using namespace std;
int n,m,x,y,z,mp[maxn][maxn],vis[maxn],d[maxn];
int prim(int mp[][maxn]){//选取0作为原点 int ans=0;for(int i=0;i<n;i++){d[i]=mp[0][i];}vis[0]=1;for(int i=1;i<n;i++){int Min=inf;int k=-1;//加入一个除了原点外的点到集合里for(int j=0;j<n;j++){if(Min>d[j] &&!vis[j]){Min=d[j];k=j;}}if(k==-1) return -1;  //图不连通ans+=Min;vis[k]=1;//松弛for(int j=0;j<n;j++)if(!vis[j]&&d[j]>mp[k][j])d[j]=mp[k][j];}return ans;
}int main(){cin>>n>>m;  //n个顶点,m条边for(int i=0;i<n;i++){for(int j=0;j<n;j++){mp[i][j]=inf;}mp[i][i]=0;}for(int i=0;i<m;i++){sf("%d%d%d",&x,&y,&z);mp[x][y]=mp[y][x]=z;} cout<<"最小生成树的代价为："<<prim(mp)<<endl;return 0;
} 

（二）最小生成树模板kruskal

//kruskal算法之最小生成树 (并查集)
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define For(a,b) for(int i=0;i<b;i++)
#define mem(x) memset(x,0,sizeof(x))
#define sf scanf
#define pf printf
#define maxn 3010
int gcd(int a,int b){ return b>0?gcd(b,a%b):a;}
typedef long long ll;
using namespace std;
struct edge{int sta,ed,cost;
}E[maxn*maxn];
int n,m;
int pa[maxn],rank[maxn];bool cmp(edge x,edge y){return x.cost<y.cost;
}
int find_set(int x){if(x!=pa[x]) {pa[x]=find_set(pa[x]);}return pa[x];
}void union_set(int x,int y){x=find_set(x);y=find_set(y);if(rank[x]>rank[y]) pa[y]=x;else {pa[x]=y;if(rank[x]==rank[y]){rank[y]++;}}
}int Same(int x,int y){return find_set(x)==find_set(y);
}
int Kruskal(){ll res=0;sort(E+1,E+1+m,cmp);for(int i=1;i<=n;i++){if(Same(E[i].sta,E[i].ed)) continue;union_set(E[i].sta,E[i].ed);res+=E[i].cost;}return res;
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>E[i].sta>>E[i].ed>>E[i].cost;}//并查集的思想解决 for(int i=1;i<=n;i++) pa[i]=i;ll res=Kruskal();cout<<res<<endl;return 0;
}