[luoguP2387] 魔法森林（LCT + 并查集）

传送门

并查集真是一个判断连通的好东西！

连通性用并查集来搞。

把每一条边按照 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

排序很关键！

如果做不出来，先排序试试。

上一篇：[luoguP1516] 青蛙的约会（扩展欧几里得）

下一篇：[luoguP1993] 小 K 的农场（差分约束 + spfa 判断负环）

---

并查集 LCT