算法-程序设计课week6-作业-D - 数据中心

Example
Input

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

Output

4

思路

最小生成树的问题，要获得每个最小生成树的最长边，用kruskal算法比较合适。

这道题解法同样很有意思，求最长边最小的情况，我们只要从最小边开始构建生成树，那么最后一条加入生成树的边就一定是最大边。

收获

1. 都是最小生成树的问题，不同算法却有不同用处，比如这次的kruskal算法，非常契合求“最大边”的题目特性。 如此看来，每种算法都有独特用途。
2. 学无止境，上学期只学了kruskal的基本内容，现在又知道了kruskal能用来巧解这类最小生成树问题，不知道还有多少隐藏技能点。
3. 说实话，我觉得多门课程间的冗余太多了。要不数据结构和程序设计干脆合并好了，所有算法相关课都合并，搞成类似高中信息学集训那样的形式（不是这说法很清楚合不合适）。这样可以降低课程开设成本，降低同学们的学习压力。

#include <algorithm>
#include <iostream>

using namespace std;
int father[50005];	//并查集
int n;				//m节点数
int m;				//m边数
struct edge {
	int u, v, w;
	inline bool operator<(const edge &in) const {
		return w < in.w;
	}
} edges[100005];

int find(int x) {
	return father[x] = x == father[x] ? x : find(father[x]);
}

int kruskal() {
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		if (find(edges[i].u) != find(edges[i].v)) {
			father[find(edges[i].u)] = find(edges[i].v);
			ans += edges[i].w;
			cnt++;
		}
		if (cnt == n - 1) {
			return i;
		}
	}
	return m - 1;
}

int main() {
	int root;
	scanf("%d %d %d", &(n), &(m), &(root));
	//初始化并查集
	for (int i = 1; i <= n; i++) father[i] = i;

	//初始化边集
	for (int i = 0; i < m; i++)
		scanf("%d %d %d", &(edges[i].u), &(edges[i].v), &(edges[i].w));

	sort(edges, edges + m);
	printf("%d\n", edges[kruskal()].w);
	return 0;
}