#include <stdio.h>#define MAX_N 1000 // 最大村庄数#define INF 0x3f3f3f3f // 定义无穷大int n, m; // n表示村庄数,m表示道路数int f[MAX_N + 1]; // 并查集数组struct Edge { // 存储边的结构体 int u, v, w;} e[MAX_N * (MAX_N - 1) / 2 + 1]; // 最多有n*(n-1)/2条边void init() { // 并查集初始化 for (int i = 1; i <= n; i++) { f[i] = i; }}int find(int x) { // 并查集查找 return f[x] == x ? x : (f[x] = find(f[x]));}int cmp(const Edge &a, const Edge &b) { // 按边权从小到大排序 return a.w < b.w;}int Kruskal() { // Kruskal算法 int ans = 0, cnt = 0; init(); // 初始化并查集 for (int i = 1; i <= m; i++) { // 按边权从小到大排序 int u = find(e[i].u), v = find(e[i].v), w = e[i].w; if (u != v) { // 如果不在同一个连通块内 f[u] = v; // 合并连通块 ans += w; // 累加边权 cnt++; // 计数器加1 if (cnt == n - 1) { break; } // 边数已达到n-1,退出循环 } } return cnt == n - 1 ? ans : -1; // 如果边数不足n-1,则说明有些村庄不能连通}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); } std::sort(e + 1, e + m + 1, cmp); // 排序 int ans = Kruskal(); // 求最小生成树的权值和 printf("%d\n", ans); return 0;}电脑显示sort不属于std请改正
时间: 2024-01-04 22:03:02 浏览: 31
可以将 `std::sort` 改为 `sort`,因为 `sort` 函数在 `<algorithm>` 头文件中定义,所以不需要加上 `std::` 前缀。修改后的代码如下:
```cpp
#include <stdio.h>
#include <algorithm>
#define MAX_N 1000 // 最大村庄数
#define INF 0x3f3f3f3f // 定义无穷大
int n, m; // n表示村庄数,m表示道路数
int f[MAX_N + 1]; // 并查集数组
struct Edge { // 存储边的结构体
int u, v, w;
} e[MAX_N * (MAX_N - 1) / 2 + 1]; // 最多有n*(n-1)/2条边
void init() { // 并查集初始化
for (int i = 1; i <= n; i++) {
f[i] = i;
}
}
int find(int x) { // 并查集查找
return f[x] == x ? x : (f[x] = find(f[x]));
}
int cmp(const Edge &a, const Edge &b) { // 按边权从小到大排序
return a.w < b.w;
}
int Kruskal() { // Kruskal算法
int ans = 0, cnt = 0;
init(); // 初始化并查集
for (int i = 1; i <= m; i++) { // 按边权从小到大排序
int u = find(e[i].u), v = find(e[i].v), w = e[i].w;
if (u != v) { // 如果不在同一个连通块内
f[u] = v; // 合并连通块
ans += w; // 累加边权
cnt++; // 计数器加1
if (cnt == n - 1) {
break;
} // 边数已达到n-1,退出循环
}
}
return cnt == n - 1 ? ans : -1; // 如果边数不足n-1,则说明有些村庄不能连通
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}
std::sort(e + 1, e + m + 1, cmp); // 排序
int ans = Kruskal(); // 求最小生成树的权值和
printf("%d\n", ans);
return 0;
}
```