现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
输入样例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
|
输出样例:
思路
可以使用并查集来做，使用结构体数组node a来存储两个村子及其公路的成本，按照成本从低到高排序，
ans记录成本，初始化为0；cnt记录可以连接的村庄数量，初始化为1；
便利数组a，判断两个村庄是否已经连通，即判断二者跟节点是否相同；如果相同，说明两个村庄已连通，该条公路不需要修建；如果不同，合并这两个村庄，ans加上修建该路的成本，cnt++;
如果cnt==n，说明全部村庄可以连通，输出ans；否则，输出-1（PS：这一步也可以通过判断连通分量的个数是否为1来判断村庄是否可以连通）
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <algorithm>
using namespace std;
struct node{
int x, y, z;
};
int fa[1005];
void init(int n) {
for(int i = 1;i <= n; i++) {
fa[i] = i;
}
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool cmp(node a, node b) {
return a.z < b.z;
}
int main() {
int n, m;
cin >> n >> m;
node a[m];
for(int i = 0; i < m; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
}
sort(a, a+m, cmp);
init(n);
int ans = 0, cnt = 1;
for(int i = 0; i < m; i++) {
int fx = find(a[i].x), fy = find(a[i].y);
if(fx != fy) {
ans += a[i].z;
fa[fx] = fy;
cnt++;
}
}
if(cnt == n) cout << ans;
else cout << "-1";
}
|
