算法思想:按照时间长短对路进行从小到大排序。依次取边并更新点的并查集,如果加入该边后1和n相连则输出这条路的时间就好。
主要/核心函数分析:int findfather(int nownode)找到newnode目前相连最上层的根节点,将newnode的父亲也赋值为根节点,最后返回根节点值。
测试数据:
6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6
运行结果:6
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 5 using namespace std; 6 int n, m; 7 8 struct road 9 { 10 int start, end, day; 11 road(int q, int w, int e) :start(q), end(w), day(e) {}; 12 }; 13 14 bool cmp(road g, road h) 15 { 16 return g.day < h.day; 17 } 18 19 int father[100001];//并查集 20 21 int findfather(int nownode) 22 { 23 int u = nownode; 24 25 //找到nownode的最跟结点 26 while (father[nownode] != nownode) 27 { 28 nownode = father[nownode]; 29 } 30 31 //目前结点的根节点也是nownode 32 father[u] = nownode; 33 34 return nownode;//返回当前节点的父亲 35 } 36 37 int main() 38 { 39 int j, k, l; 40 cin >> n >> m;//枢纽数量,隧道数量 41 42 vector<road>roadlist;//隧道参数 43 44 while (m--) 45 { 46 cin >> j >> k >> l; 47 roadlist.push_back(road(j, k, l)); 48 } 49 50 //并查集初始化 51 for (int i = 0; i < n; i++) 52 father[i] = i; 53 54 //由小到大排序,保证1和n连接时的路径的天数是所有前面路径的最大值 55 sort(roadlist.begin(), roadlist.end(), cmp); 56 57 for (auto y : roadlist) 58 { 59 //这条边将两边根节点连接连接,相当于把y.start所有的点的父亲都变为y.end的父亲 60 father[findfather(y.start)] = findfather(y.end); 61 62 //1和n连接,则结束 63 if (findfather(1) == findfather(n)) 64 { 65 cout << y.day;//目前该条路径的天数,就是前面所有的最大值 66 return 0; 67 } 68 } 69 }