ccf 201703-4 地铁修建(95)(并查集)

时间:2021-03-03 21:32:33

ccf 201703-4 地铁修建(95)

  使用并查集,将路径按照耗时升序排列,依次加入路径,直到1和n连通,这时加入的最后一条路径,就是所需要修建的时间最长的路径。

ccf 201703-4 地铁修建(95)(并查集)ccf 201703-4 地铁修建(95)(并查集)
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 100000+10;
 6 const int maxm = 200000+10;
 7 long n,m;
 8 struct node{
 9     long ci,cj,cij;
10 }Edge[maxm];
11 long pro[maxn];
12 bool compare(node a,node b)
13 {
14     return a.cij<=b.cij;
15 }
16 
17 long find(long a)
18 {
19     if(pro[a] == a)
20     {
21         return pro[a];
22     }
23     pro[a] = find(pro[a]);//进行路径压缩 
24     return pro[a]; 
25 }
26 
27 void unionIJ(long a,long b)
28 {
29     long pa = find(a);//找到a的祖先,并且在查找的过程中进行路径压缩
30     long pb = find(b); 
31     pro[pb] = pa;
32 }
33 int main()
34 {
35     cin>>n>>m;
36     for(long i=0;i<m;i++)
37     {
38         cin>>Edge[i].ci>>Edge[i].cj>>Edge[i].cij;
39     }
40     sort(Edge,Edge+m,compare);
41     //从最短的路开始,建立并查集
42     for(long i=1;i<=n;i++)
43     {
44         pro[i] = i;
45     }
46     for(long i=0;i<m;i++)
47     {
48         ///将ci和cj的祖先合并
49         unionIJ(Edge[i].ci,Edge[i].cj); 
50         //判断1和n是否联通
51         if(find(1) == find(n))
52         {
53             cout<<Edge[i].cij<<endl;
54             break; 
55          } 
56      } 
57     return 0;
58 }
View Code

ccf 201703-4 地铁修建(95)(并查集)