C语言-算法-最小生成树

【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 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; // 返回最小生成树的权重
}