乌海网站开发广告媒体资源平台

【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例 #1

样例输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

样例输出 #1

7

提示

数据规模：

对于 $20\%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40\%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70\%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100\%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i\le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

代码

#include <stdio.h>
#include <stdlib.h>
#define MAXN 300000
#define MAXM 300000
typedef struct // 定义边的结构体
{int u, v, w;
}Edge;
Edge edges[MAXM]; // 存储所有的边
int pa[MAXN]; // 并查集数组，用于判断两个节点是否在同一棵树中
int N, M; // N是节点数，M是边数
int cmp(Edge a, Edge b); // 边的比较函数，按照边的权重从小到大排序
int find(int x); // 并查集的查找函数，用于查找节点x的根节点
int kruskal(); // Kruskal算法函数int main(int argc, char *argv[])
{int i;scanf("%d %d", &N, &M); // 读取节点数和边数for (i = 0; i < M; i++){scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);}int res = kruskal(); // 调用Kruskal算法计算最小生成树的权重if (res == -1) // 如果图不连通{printf("orz\n");}else{printf("%d\n", res);}return 0;
}int cmp(Edge a, Edge b) // 边的比较函数，按照边的权重从小到大排序
{return (a.w - b.w);
}int find(int x) // 并查集的查找函数，用于查找节点x的根节点
{while (pa[x] != x){x = pa[x];}return x; 
}int kruskal() // Kruskal算法函数
{int i, j;for (i = 0; i < M; i++) // 将所有的边按照从小到大排序{for (j = i + 1; j < M; j++){if (cmp(edges[i], edges[j]) > 0){Edge temp = edges[i];edges[i] = edges[j];edges[j] = temp;}}}for (i = 1; i <= N; i++) // 初始化并查集{pa[i] = i;}int res = 0; // 存储最小生成树的权重int cnt = 0; // 存储当前已经选择的边的数量for (i = 0; i < M; i++) // 遍历所有的边{int u = find(edges[i].u); // 边的一个节点int v = find(edges[i].v); // 边的另一个节点// 如果两个节点不在同一棵树中，说明这条边可以添加到最小生成树中if (u != v){res += edges[i].w; // 更新最小生成树的权重pa[u] = v; // 合并两棵树cnt++; // 更新已经选择的边的数量}}if (cnt != N - 1) // 如果选择边的数量小于N - 1，说明图不连通{return -1;}return res; // 返回最小生成树的权重
}