CCF CSP 201412-4.最优灌溉

问题描述

　　雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。
　　为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。
　　现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

　　输入的第一行包含两个正整数n, m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。
　　接下来m行，每行包含三个整数ai, bi, ci，表示第ai片麦田与第bi片麦田之间可以建立一条水渠，所需要的费用为ci。

输出格式

　　输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

样例输入

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

样例输出

6

样例说明

　　建立以下三条水渠：麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。

评测用例规模与约定

　　前20%的评测用例满足：n≤5。
　　前40%的评测用例满足：n≤20。
　　前60%的评测用例满足：n≤100。
　　所有评测用例都满足：1≤n≤1000，1≤m≤100,000，1≤ci≤10,000。

---

分析：

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

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

typedef struct Node {
	// 边的两个端点
	int u, v;
	// 边的权值(所需的费用)
	int w;
} Edge;

Edge edge[100000];
// 并查集
int usf[1001];

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

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

int kruskal(int n, int m) {
	for (int i = 1; i <= n; i++) {
		usf[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) {
			usf[u] = v;
			// 最小生成树中的权值之和
			result += edge[i].w;
			count++;
		}
		if (count == n - 1) {
			break;
		}
	}
	return result;
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	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);
	return 0;
}