传送门
并查集真是一个判断连通的好东西！
连通性用并查集来搞。
把每一条边按照 a 为关键字从小到大排序。
那么直接枚举，动态维护 b 的最小生成树
用 a[i] + 1 ~ n 路径上最大的 b[i] 更新答案即可
——代码
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define N 200005 5 #define get(x) (son[f[x]][1] == (x)) 6 #define min(x, y) ((x) < (y) ? (x) : (y)) 7 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) 8 #define isroot(x) (son[f[x]][0] ^ (x) && son[f[x]][1] ^ (x)) 9 10 int n, m, ans = ~(1 << 31); 11 int mx[N], rev[N], fa[N], f[N], val[N], son[N][2], s[N]; 12 13 struct node 14 e[N]; 17 18 inline int read() 19 26 27 inline bool cmp(node x, node y) 28 31 32 inline int getf(int x) 33 36 37 inline void update(int x) 38 45 } 46 47 inline void pushdown(int x) 48 56 } 57 58 inline void rotate(int x) 59 75 76 inline void splay(int x) 77 86 87 inline void access(int x) 88 91 92 inline void reverse(int x) 93 98 99 inline void cut(int x, int y) 100 107 108 inline void link(int x, int y) 109 114 115 inline int find(int x) 116 122 123 inline int query(int x, int y) 124 130 131 int main() 132 147 if(getf(1) ^ getf(n)) 148 152 std::sort(e + 1, e + m + 1, cmp); 153 for(i = 1; i <= m; i++) 154 158 for(i = 1; i <= n; i++) fa[i] = i; 159 for(i = 1; i <= m; i++) 160 171 else 172 181 } 182 if(getf(1) == getf(n)) ans = min(ans, e[i].a + val[query(1, n)]); 183 } 184 printf("%d\n", ans); 185 return 0; 186 }View Code
排序很关键！
如果做不出来，先排序试试。
上一篇：[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）
下一篇：[luoguP2045] 方格取数加强版（最小费用最大流）
LCT 并查集
