前言

最小生成树又称 $MST$，为边权和最小的生成树。

$Kruskal$

#include <bits/stdc++.h>//万能头文件
using namespace std;//命名空间
int fa[1000001];
int n, m, res, cnt;
struct poi{
	int u, v, w;
}g[1000001];
bool cmp(poi a, poi b)
{
	return a.w < b.w;
}
int find(int x)//并查集 
{
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}
int main()//主函数
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
	stable_sort(g + 1, g + m + 1, cmp);//排序
	for(int i = 1; i <= n; i++) fa[i] = i;//并查集初始化 
	for(int i = 1; i <= m; i++){
		int x = find(g[i].u);//并查集 
		int y = find(g[i].v);//并查集 
		if(x == y) continue;//若出现两个点已经联通了，那么这一条边就不需要了
		fa[x] = y;//将y、x合并 
		res += g[i].w;//将边权计入答案
		cnt++;//边数++ 
	}
	if(cnt == n - 1) cout << res;
	else cout << "No MST";//没有最小生成树 
	return 0;//华丽结束
}

$Prim$

$O(n^2)$

#include <bits/stdc++.h>//万能头文件
using namespace std;//命名空间
bool vis[1001];
int n, m, res;
int a[1001][1001], d[1001];
void prim()
{
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[1] = 0;
	for(int i = 1; i <= n; i++){
		int x = 0;
		for(int j = 1; j <= n; j++){
			if(!vis[j] && d[j] < d[x]) x = j;
		}
		vis[x] = 1;
		for(int j = 1; j <= n; j++){
			if(!vis[j]) d[j] = min(d[j], a[x][j]);
		}
	}
}
int main()//主函数
{
	memset(a, 0x3f, sizeof(a));
	cin >> n >> m;
	for(int i = 1; i <= n; i++) a[i][i] = 0;
	for(int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		a[u][v] = a[v][u] = min(a[u][v], w);
	}
	prim();
	for(int i = 2; i <= n; i++) res += d[i];
	cout << res;
	return 0;//华丽结束
}