Prim

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5e2 + 10;
int T = 1, n, m, u, v, w, dis[N], e[N][N];
bool vis[N];
void Prim(){
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++){
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!vis[j] && (t == -1 || dis[j] < dis[t]))
				t = j;
		if (dis[t] == INF){  //考虑到自环的情况（例如 4 4 3，点 4 到点 4 的距离是 3，那就会出问题），所以先判断
			cout << "impossible\n";
			return;
		}
		vis[t] = true;
		ans += dis[t];
		for (int j = 1; j <= n; j++)
			dis[j] = min(dis[j], e[t][j]);
	}
	cout << ans << "\n";
}
void solve(){
	scanf("%d%d", &n, &m);
	memset(e, 0x3f, sizeof(e));
	for (int i = 1; i <= m; i++){
		scanf("%d%d%d", &u, &v, &w);
		e[u][v] = e[v][u] = min(e[u][v], w);
	}
	Prim();
}
int main(){
//	cin >> T;
	while (T--)
		solve();
	return 0;
}

Kruskal

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int T = 1, n, m, fa[N];
struct Edge{
	int u, v, w;
	bool operator < (const Edge &x)const{
		return w < x.w;
	}
}e[N];
int find(int x){
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void Kruskal(){
	sort(e + 1, e + m + 1);
	for (int i = 1; i <= m; i++)
		fa[i] = i;
	int ans = 0, cnt = 0;
	for (int i = 1; i <= m; i++){
		int x = find(e[i].u), y = find(e[i].v);
		if (x != y){
			fa[x] = y;
			ans += e[i].w;
			cnt++;
		}
	}
	if (cnt < n - 1) cout << "impossible\n";
	else cout << ans << "\n";
}
void solve(){
	scanf("%d%d", &n, &m);
	memset(e, 0x3f, sizeof(e));
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	Kruskal();
}
int main(){
//	cin >> T;
	while (T--)
		solve();
	return 0;
}

模板：
https://www.acwing.com/problem/content/860/
https://www.acwing.com/problem/content/861/
https://www.luogu.com.cn/problem/P3366