CCF CSP 201812-4.数据中心

样例输入

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

样例输出

4

样例说明

　　下图是样例说明。

---

分析：

本题考察最小生成树，题目要求的是最小生成树中，最大的边权。可以采用kruskal算法求解。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef struct Node {
	int u, v; // 两个端点的编号
	int w; //权重
} Edge;

// 10^5过大，应该在main函数之外定义
Edge edge[100000];
// 并查集
int ufs[500001];

int find(int x) {
	int a = x;
	while (x != ufs[x]) {
		x = ufs[x];
	}
	// 路径压缩
	while (a != ufs[a]) {
		int z = a;
		a = ufs[a];
		ufs[z] = x;
	}
	return x;
}

bool cmp(Edge a, Edge b) {
	return a.w < b.w;
}

int kruskal(int n, int m) {
	for (int i = 1; i <= n; i++) {
		ufs[i] = i;
	}

	sort(edge, edge + m, cmp);
	int count = 0, result = 0;
	for (int i = 0; i < m; i++) {
		int u = find(edge[i].u);
		int v = find(edge[i].v);
		if (u != v) {
			// 寻找最小生成树中的最大边权
			result = max(result, edge[i].w);
			ufs[u] = v;
			count++;
		}
		if (count == n - 1) {
			break;
		}
	}
	return result;
}

int main() {
	int n, m, root;
	scanf("%d %d %d", &n, &m, &root);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
	}
	int result = kruskal(n, m);
	printf("%d\n", result);
}