题解

芜湖~

#include<bits/stdc++.h>  
using namespace std;  
  
// fa数组用于并查集，表示每个节点的父节点（实际上，在这里是根节点），用于快速查找节点所属的集合  
// n表示节点数，w表示边数，num数组用于统计每个集合中的节点数  
int fa[209], n, w, num[209];  
  
// 定义边结构体，包含起点u，终点v，权重w，以及边的索引id  
struct node {  
	int u, v, w, id;  
}a[6009];  
  
// 比较函数，用于对边按权重进行排序  
bool cmp(node A, node B) {  
	return A.w < B.w;  
}  
  
// 获取节点x的根节点（即所属的集合）  
int get(int x) {  
	if (fa[x] == x) return x;  
	return fa[x] = get(fa[x]); // 路径压缩，提高查找效率  
}  
  
// 合并节点x和y所在的集合  
void merge(int x, int y) {  
	fa[get(x)] = get(y);  
}  
  
// 尝试以第up条边作为最后一条边来构建最小生成树  
void solve(int up) {  
	// 初始化并查集和节点计数  
	for (int i = 1; i <= n; i++) fa[i] = i, num[i] = 0; 
	 
	int ans = 0; // 用于存储当前构建的最小生成树的权重和  
	  
	// 遍历所有边，但只考虑id小于等于up的边  
	for (int i = 0; i < w; i++) {  
		if (a[i].id > up) continue; // 如果边的id大于up，则跳过  
		if (get(a[i].u) == get(a[i].v)) continue; // 如果u和v已经在同一个集合中，则跳过这条边  
		merge(a[i].u, a[i].v); // 合并u和v所在的集合  
		ans += a[i].w; // 将这条边的权重加到最小生成树的权重和中  
	}  
	  
	// 统计每个集合中的节点数  
	for (int i = 1; i <= n; i++) num[get(i)]++;  
	  
	// 检查是否存在一个集合包含了所有节点（即集合大小为n）  
	for (int i = 1; i <= n; i++) {  
		if (num[i] == n) {  
			cout << ans << '\n'; // 如果存在，输出当前的最小生成树权重和  
			return;  
		}  
	}  
	cout << -1 << '\n'; // 如果不存在，说明无法以第up条边作为最后一条边来构建包含所有节点的最小生成树  
}  
  
int main() {  
	cin >> n >> w; // 输入节点数和边数  
	for (int i = 0; i < w; i++) {  
		cin >> a[i].u >> a[i].v >> a[i].w; // 输入每条边的起点、终点和权重  
		a[i].id = i; // 设置边的索引  
	}  
	sort(a, a + w, cmp); // 对边按权重进行排序  
	  
	// 对每一条边都尝试作为最后一条边来构建最小生成树  
	for (int i = 0; i < w; i++) solve(i);  
	return 0;  
}

阿巴阿巴。