ccf 201703-4 地铁修建(95)
使用并查集,将路径按照耗时升序排列,依次加入路径,直到1和n连通,这时加入的最后一条路径,就是所需要修建的时间最长的路径。
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 }