最小生成树数模板（kruscal算法和prime算法）

kruscal算法

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边 int fat[200010];//记录集体老大 struct node { int from,to,dis;//结构体储存边 }edge[200010]; bool cmp(const node &a,const node &b)//sort排序（当然你也可以快排） { return a.dis<b.dis; } int father(int x)//找集体老大，并查集的一部分 { if(fat[x]!=x) return father(fat[x]); else return x; } void unionn(int x,int y)//加入团体，并查集的一部分 { fat[father(y)]=father(x); } int main() { scanf("%d%d",&n,&m);//输入点数，边数 for(int i=1;i<=m;i++) { scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息 } for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化） sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现） for(int i=1;i<=m;i++)//从小到大遍历 { if(k==n-1) break;//n个点需要n-1条边连接 if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体 { unionn(edge[i].from,edge[i].to);//加入 tot+=edge[i].dis;//记录边权 k++;//已连接边数+1 } } printf("%d",tot); return 0; }

prime算法

#include <bits/stdc++.h> using namespace std; int n, m; int e[5005][5005], book[5005]; int dis[5005]; int inf = 0x3f3f3f3f; int ans = 0; int prime() { book[1] = 1; for(int i = 1; i < n; i++) { int minn = inf; int u = 0; for(int j = 1; j <= n; j++) { if(book[j] == 0 && dis[j] < minn) { minn = dis[j]; u = j; } } if(u == 0) return -1; //如果不连通返回-1 book[u] = 1; ans += dis[u]; for(int j = 1; j <= n; j++) { if(book[j] == 0 && e[u][j] < dis[j]) dis[j] = e[u][j]; } } return ans; } int main() { cin >> n >> m; memset(book, 0, sizeof(book)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j) e[i][j] = 0; else e[i][j] = inf; } } for(int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; if(z < e[x][y]) //！！！不要忘记判断！！！ e[x][y] = e[y][x] = z; //！！！不要忘记是无向图 } for(int i = 1; i <= n; i++) dis[i] = e[1][i]; int res = prime(); if(res == -1) cout << "orz"; else cout << res; return 0; }