csp 201703_4 地铁修建

摘要:

并查集

问题描述

​ A市有n个交通枢纽,其中1号和n号非常重要,为了加强运输能力,A市决定在1号到n号枢纽间修建一条地铁。
  地铁由很多段隧道组成,每段隧道连接两个交通枢纽。经过勘探,有m段隧道作为候选,两个交通枢纽之间最多只有一条候选的隧道,没有隧道两端连接着同一个交通枢纽。
  现在有n家隧道施工的公司,每段候选的隧道只能由一个公司施工,每家公司施工需要的天数一致。而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。
  作为项目负责人,你获得了候选隧道的信息,现在你可以按自己的想法选择一部分隧道进行施工,请问修建整条地铁最少需要多少天。

输入格式

​ 输入的第一行包含两个整数n, m,用一个空格分隔,分别表示交通枢纽的数量和候选隧道的数量。
  第2行到第m+1行,每行包含三个整数a, b, c,表示枢纽a和枢纽b之间可以修建一条隧道,需要的时间为c天。

输出格式

​ 输出一个整数,修建整条地铁线路最少需要的天数。

样例输入

6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6

样例输出

6

样例说明

​ 可以修建的线路有两种。
  第一种经过的枢纽依次为1, 2, 3, 6,所需要的时间分别是4, 4, 7,则整条地铁线需要7天修完;
  第二种经过的枢纽依次为1, 4, 5, 6,所需要的时间分别是2, 5, 6,则整条地铁线需要6天修完。
  第二种方案所用的天数更少。

评测用例规模与约定

​ 对于20%的评测用例,1 ≤ n ≤ 10,1 ≤ m ≤ 20;
  对于40%的评测用例,1 ≤ n ≤ 100,1 ≤ m ≤ 1000;
  对于60%的评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 10000,1 ≤ c ≤ 1000;
  对于80%的评测用例,1 ≤ n ≤ 10000,1 ≤ m ≤ 100000;
  对于100%的评测用例,1 ≤ n ≤ 100000,1 ≤ m ≤ 200000,1 ≤ a, bn,1 ≤ c ≤ 1000000。

  所有评测用例保证在所有候选隧道都修通时1号枢纽可以通过隧道到达其他所有枢纽。

思路

将所有的边按照长度从短到长排序,然后依次从短到长将边取出,被连在一起的节点形成一个集合,当1号节点和n号节点同时出现在同一个集合时,输出最后选中的那个边的长度即为所求。

有两点需要注意:

  1. 并查集的findFather函数一定要进行路径压缩,否则会超时。压缩前节点是在一条链上,需要一层一层地向上找根节点,压缩方法是,在每次通过findFather找到根节点后,将路径上经过的所有节点都转化为根节点的直接儿子。
  2. sort函数的第二个参数,应该是数组的最后一个元素的再下一个空间的地址。

AC代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge
{
int s, t;
int len;
};

int father[100005] = {0};
Edge edges[200005];

int findFather(int a){
int x = a;
int old_father;
while(father[a] != a){
a = father[a];
}
//路径压缩
old_father = father[x];
while(old_father != a){
father[x] = a;
x = old_father;
old_father = father[x];
}
return a;
}

//将两个集合合并
void unionSet(int a, int b){
int a_father = findFather(a);
int b_father = findFather(b);
if(a_father != b_father){
father[a_father] = b_father;
}
}

bool cmp(Edge e1, Edge e2){
return e1.len < e2.len;
}

int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
father[i] = i;
}
for(int i=1; i<=m; i++){
Edge e;
cin >> e.s >> e.t >> e.len;
edges[i] = e;
}
sort(&edges[1], &edges[m+1], cmp);//注意第二个参数应该是m+1而不是m
for(int i=1; i<=m; i++){
unionSet(edges[i].s, edges[i].t);
if(findFather(1) == findFather(n)){
cout << edges[i].len;
return 0;
}
}
}