这道题以前zbtrs大佬给我讲过。但是我只知道思想，不知道要lct维护...
这个套路很常见。
题意：给你一个无向图，每条边有a，b两个权值。求1到n号点的一条路径，路径的权值是每条边的最大a与最大b之和。求可能的最小权值。无解输出-1。
解：有个很朴素的想法是爆搜......
有个很朴素(??)的想法，最后路径的a最大值一定是某条边的a，于是我们枚举这个a，每次把小于a的边都加进去，然后若1，n连通就跑b的最短路。这样就有50分了。
然后我们发现每次跑最短路的时间不可承受，如何优化呢？
我们肯定会在某一时刻加出环，然后我们发现这个环上的a的大小是无关紧要的，我们把环上b最大的边去掉，这样就是一棵树了。
然后用lct实行这个操作，时间复杂度mlog(n + m)。
注意这里没有点权，只有边权，而且边全都给出来了，我们就对于每个边新建一个点代表它就行了...具体看代码。
1 // NOI 2014 mofa forest 2 #include <cstdio> 3 #include <algorithm> 4 5 const int N = 50010, M = 100010, INF = 0x7f7f7f7f; 6 7 inline void read(int &x) { 8 char c = getchar(); 9 bool f = 0; 10 while(c < '0' || c > '9') { 11 if(c == '-') { 12 f = 1; 13 } 14 c = getchar(); 15 } 16 while(c >= '0' && c <= '9') { 17 x = (x << 3) + (x << 1) + c - 48; 18 c = getchar(); 19 } 20 if(f) { 21 x = -x; 22 } 23 return; 24 } 25 26 struct Edge { 27 int u, v; 28 int a, b; 29 inline bool operator <(const Edge &d) const { 30 if(a != d.a) { 31 return a < d.a; 32 } 33 return b < d.b; 34 } 35 }edge[M]; 36 37 struct UFS { 38 int fa[N + M]; 39 40 inline void clear() { 41 for(int i = 1; i < N + M; i++) { 42 fa[i] = i; 43 } 44 return; 45 } 46 47 UFS() { 48 clear(); 49 } 50 51 inline int find(int x) { 52 if(fa[x] == x) { 53 return x; 54 } 55 return fa[x] = find(fa[x]); 56 } 57 58 inline void merge(int x, int y) { 59 fa[find(x)] = find(y); 60 return; 61 } 62 63 inline bool check(int x, int y) { 64 return find(x) == find(y); 65 } 66 }ufs; 67 68 struct LCT { 69 int val[N + M], fa[N + M], s[N + M][2], large[N + M], stk[N + M], t; 70 bool rev[N + M]; 71 72 inline int no_root(int x) { 73 return s[fa[x]][0] == x || s[fa[x]][1] == x; 74 } 75 76 inline void pushup(int x) { 77 large[x] = x; 78 if(val[large[x]] < val[large[s[x][0]]]) { 79 large[x] = large[s[x][0]]; 80 } 81 if(val[large[x]] < val[large[s[x][1]]]) { 82 large[x] = large[s[x][1]]; 83 } 84 return; 85 } 86 87 inline void pushdown(int x) { 88 if(!rev[x]) { 89 return; 90 } 91 if(s[x][0]) { 92 rev[s[x][0]] ^= 1; 93 } 94 if(s[x][1]) { 95 rev[s[x][1]] ^= 1; 96 } 97 std::swap(s[x][0], s[x][1]); 98 rev[x] = 0; 99 return; 100 } 101 102 inline void rotate(int x) { 103 int y = fa[x]; 104 int z = fa[y]; 105 bool f = (s[y][1] == x); 106 107 fa[x] = z; 108 if(no_root(y)) { 109 s[z][s[z][1] == y] = x; 110 } 111 s[y][f] = s[x][!f]; 112 fa[s[x][!f]] = y; 113 s[x][!f] = y; 114 fa[y] = x; 115 116 pushup(y); 117 pushup(x); 118 return; 119 } 120 121 inline void splay(int x) { 122 int y = x; 123 stk[++t] = x; 124 while(no_root(y)) { 125 y = fa[y]; 126 stk[++t] = y; 127 } 128 while(t) { 129 pushdown(stk[t]); 130 t--; 131 } 132 y = fa[x]; 133 int z = fa[y]; 134 while(no_root(x)) { 135 if(no_root(y)) { 136 (s[z][1] == y) ^ (s[y][1] == x) ? 137 rotate(x) : rotate(y); 138 } 139 rotate(x); 140 y = fa[x]; 141 z = fa[y]; 142 } 143 return; 144 } 145 146 inline void access(int x) { 147 int y = 0; 148 while(x) { 149 splay(x); 150 s[x][1] = y; 151 pushup(x); 152 y = x; 153 x = fa[x]; 154 } 155 return; 156 } 157 158 inline int findroot(int x) { 159 access(x); 160 splay(x); 161 pushdown(x); 162 while(s[x][0]) { 163 x = s[x][0]; 164 pushdown(x); 165 } 166 return x; 167 } 168 169 inline void makeroot(int x) { 170 access(x); 171 splay(x); 172 rev[x] = 1; 173 return; 174 } 175 176 inline void link(int x, int y) { 177 makeroot(x); 178 if(findroot(y) != x) { 179 fa[x] = y; 180 } 181 return; 182 } 183 184 inline void cut(int x, int y) { 185 makeroot(x); 186 access(y); 187 splay(y); 188 if(s[y][0] == x && fa[x] == y && s[x][1] == 0) { 189 fa[x] = 0; 190 s[y][0] = 0; 191 pushup(y); 192 } 193 return; 194 } 195 196 inline int getmax(int x, int y) { 197 makeroot(x); 198 access(y); 199 splay(y); 200 return large[y]; 201 } 202 }lct; 203 204 int main() { 205 int n, m, ans = INF; 206 scanf("%d%d", &n, &m); 207 for(int i = 1; i <= m; i++) { 208 read(edge[i].u); 209 read(edge[i].v); 210 read(edge[i].a); 211 read(edge[i].b); 212 } 213 std::sort(edge + 1, edge + m + 1); 214 for(int i = 1; i <= m; i++) { 215 lct.val[i + n] = edge[i].b; 216 } 217 218 for(int i = 1; i <= m; i++) { 219 int x = edge[i].u; 220 int y = edge[i].v; 221 //printf("%d - %d a = %d b = %d ", x, y, edge[i].a, edge[i].b); 222 if(ufs.check(x, y)) { 223 int t = lct.getmax(x, y); 224 if(lct.val[t] > edge[i].b) { 225 lct.cut(edge[t - n].u, t); 226 lct.cut(edge[t - n].v, t); 227 lct.link(x, i + n); 228 lct.link(y, i + n); 229 if(ufs.check(1, n)) { 230 ans = std::min(ans, edge[i].a + lct.val[lct.getmax(1, n)]); 231 } 232 //printf("1 : ans = %d ", ans); 233 } 234 } 235 else { 236 ufs.merge(x, y); 237 lct.link(x, i + n); 238 lct.link(y, i + n); 239 if(ufs.check(1, n)) { 240 ans = std::min(ans, edge[i].a + lct.val[lct.getmax(1, n)]); 241 //printf("2 : ans = %d ", ans); 242 } 243 } 244 } 245 printf("%d", ans == INF ? -1 : ans); 246 return 0; 247 }
update：前面15分是搜索，50分是枚举一条边，暴力维护生成树。70分是枚举a的取值，并查集维护。看代码吧。
1 #include <bits/stdc++.h> 2 3 const int N = 200010, INF = 0x3f3f3f3f; 4 5 struct Edge { 6 int nex, v, a, b, pre; 7 }edge[N << 1]; int tp = 1; 8 9 struct Node { 10 int a, b, x, y; 11 inline bool operator < (const Node &w) const { 12 return a < w.a; 13 } 14 }node[N << 1]; 15 16 int e[N], n, m; 17 std::multiset<int> st; 18 19 inline void add(int x, int y, int a, int b) { 20 tp++; 21 edge[tp].v = y; 22 edge[tp].a = a; 23 edge[tp].b = b; 24 edge[tp].nex = e[x]; 25 if(e[x]) edge[e[x]].pre = tp; 26 e[x] = tp; 27 return; 28 } 29 30 inline void del(int x, int i) { 31 if(!edge[i].nex && e[x] == i) { 32 e[x] = 0; 33 } 34 else if(!edge[i].nex) { 35 edge[edge[i].pre].nex = 0; 36 } 37 else if(e[x] == i) { 38 e[x] = edge[i].nex; 39 edge[e[x]].pre = 0; 40 } 41 else { 42 edge[edge[i].pre].nex = edge[i].nex; 43 edge[edge[i].nex].pre = edge[i].pre; 44 } 45 return; 46 } 47 48 inline void Link() { 49 for(int i = 1; i <= m; i++) { 50 add(node[i].x, node[i].y, node[i].a, node[i].b); 51 add(node[i].y, node[i].x, node[i].a, node[i].b); 52 } 53 return; 54 } 55 56 namespace bf { 57 int ans = INF; 58 bool vis[N]; 59 void DFS(int x, int a, int b) { 60 if(x == n) { 61 ans = std::min(ans, a + b); 62 return; 63 } 64 vis[x] = 1; 65 for(int i = e[x]; i; i = edge[i].nex) { 66 int y = edge[i].v; 67 if(vis[y]) continue; 68 DFS(y, std::max(a, edge[i].a), std::max(b, edge[i].b)); 69 } 70 vis[x] = 0; 71 return; 72 } 73 inline void solve() { 74 Link(); 75 DFS(1, 0, 0); 76 if(ans == INF) ans = -1; 77 printf("%d ", ans); 78 return; 79 } 80 } 81 82 namespace ufs { 83 int fa[N]; 84 inline void init() { 85 for(int i = 1; i <= n; i++) fa[i] = i; 86 return; 87 } 88 int find(int x) { 89 if(fa[x] == x) return x; 90 return fa[x] = find(fa[x]); 91 } 92 inline void merge(int x, int y) { 93 fa[find(x)] = find(y); 94 return; 95 } 96 inline bool check(int x, int y) { 97 return find(x) == find(y); 98 } 99 } 100 101 namespace bf2 { 102 int Time, large, pos, vis[N]; 103 bool DFS(int x, int t) { 104 if(x == t) return true; 105 vis[x] = Time; 106 for(int i = e[x]; i; i = edge[i].nex) { 107 int y = edge[i].v; 108 if(vis[y] == Time) continue; 109 if(DFS(y, t)) { 110 if(large < edge[i].b) { 111 large = edge[i].b; 112 pos = i; 113 } 114 return true; 115 } 116 } 117 return false; 118 } 119 int getMax(int x) { 120 if(x == n) return 0; 121 vis[x] = Time; 122 for(int i = e[x]; i; i = edge[i].nex) { 123 int y = edge[i].v; 124 if(vis[y] == Time) continue; 125 int t = getMax(y); 126 if(t == -1) continue; 127 return std::max(t, edge[i].b); 128 } 129 return -1; 130 } 131 inline void solve() { 132 int ans = INF; 133 ufs::init(); 134 for(int i = 1; i <= m; i++) { 135 int x = node[i].x, y = node[i].y; 136 if(ufs::check(x, y)) { 137 large = -1; 138 ++Time; 139 DFS(x, y); 140 if(large <= node[i].b) continue; 141 del(edge[pos ^ 1].v, pos); 142 del(edge[pos].v, pos ^ 1); 143 add(x, y, node[i].a, node[i].b); 144 add(y, x, node[i].a, node[i].b); 145 } 146 else { 147 ufs::merge(x, y); 148 add(x, y, node[i].a, node[i].b); 149 add(y, x, node[i].a, node[i].b); 150 } 151 if(ufs::check(1, n)) { 152 ++Time; 153 int temp = getMax(1); 154 ans = std::min(ans, node[i].a + temp); 155 } 156 } 157 if(ans == INF) ans = -1; 158 printf("%d ", ans); 159 return; 160 } 161 } 162 163 namespace bf3 { 164 inline bool cmp(const Node &x, const Node &y) { 165 return x.b < y.b; 166 } 167 inline void solve() { 168 std::sort(node + 1, node + m + 1, cmp); 169 int ans = INF; 170 for(int lim = 1; lim <= 30; lim++) { 171 ufs::init(); 172 int temp = INF; 173 for(int i = 1; i <= m; i++) { 174 if(node[i].a > lim) { 175 continue; 176 } 177 ufs::merge(node[i].x, node[i].y); 178 if(ufs::check(1, n)) { 179 temp = node[i].b; 180 break; 181 } 182 } 183 ans = std::min(ans, lim + temp); 184 } 185 if(ans == INF) ans = -1; 186 printf("%d ", ans); 187 return; 188 } 189 } 190 191 namespace lct { 192 int fa[N], s[N][2], large[N], val[N], stk[N], top; 193 bool rev[N]; 194 inline bool no_root(int x) { 195 return s[fa[x]][0] == x || s[fa[x]][1] == x; 196 } 197 inline void pushup(int x) { 198 large[x] = x; 199 if(s[x][0] && val[large[x]] < val[large[s[x][0]]]) { 200 large[x] = large[s[x][0]]; 201 } 202 if(s[x][1] && val[large[x]] < val[large[s[x][1]]]) { 203 large[x] = large[s[x][1]]; 204 } 205 return; 206 } 207 inline void pushdown(int x) { 208 if(rev[x]) { 209 if(s[x][0]) rev[s[x][0]] ^= 1; 210 if(s[x][1]) rev[s[x][1]] ^= 1; 211 std::swap(s[x][0], s[x][1]); 212 rev[x] = 0; 213 } 214 return; 215 } 216 inline void rotate(int x) { 217 int y = fa[x]; 218 int z = fa[y]; 219 bool f = (s[y][1] == x); 220 221 fa[x] = z; 222 if(no_root(y)) { 223 s[z][s[z][1] == y] = x; 224 } 225 s[y][f] = s[x][!f]; 226 if(s[x][!f]) { 227 fa[s[x][!f]] = y; 228 } 229 s[x][!f] = y; 230 fa[y] = x; 231 232 pushup(y); 233 return; 234 } 235 inline void splay(int x) { 236 int y = x; 237 stk[top = 1] = y; 238 while(no_root(y)) { 239 y = fa[y]; 240 stk[++top] = y; 241 } 242 while(top) { 243 pushdown(stk[top]); 244 top--; 245 } 246 247 y = fa[x]; 248 int z = fa[y]; 249 while(no_root(x)) { 250 if(no_root(y)) { 251 (s[z][1] == y) ^ (s[y][1] == x) ? 252 rotate(x) : rotate(y); 253 } 254 rotate(x); 255 y = fa[x]; 256 z = fa[y]; 257 } 258 pushup(x); 259 return; 260 } 261 inline void access(int x) { 262 int y = 0; 263 while(x) { 264 splay(x); 265 s[x][1] = y; 266 pushup(x); 267 y = x; 268 x = fa[x]; 269 } 270 return; 271 } 272 inline void make_root(int x) { 273 access(x); 274 splay(x); 275 rev[x] ^= 1; 276 return; 277 } 278 inline int find_root(int x) { 279 access(x); 280 splay(x); 281 while(s[x][0]) { 282 x = s[x][0]; 283 pushdown(x); 284 } 285 splay(x); 286 return x; 287 } 288 inline void link(int x, int y) { 289 make_root(x); 290 fa[x] = y; 291 return; 292 } 293 inline void cut(int x, int y) { 294 make_root(x); 295 access(y); 296 splay(y); 297 fa[x] = s[y][0] = 0; 298 pushup(y); 299 return; 300 } 301 inline int ask(int x, int y) { 302 make_root(x); 303 access(y); 304 splay(y); 305 return large[y]; 306 } 307 } 308 309 int main() { 310 scanf("%d%d", &n, &m); 311 int largeA = -1; 312 for(int i = 1; i <= m; i++) { 313 scanf("%d%d%d%d", &node[i].x, &node[i].y, &node[i].a, &node[i].b); 314 largeA = std::max(largeA, node[i].a); 315 } 316 std::sort(node + 1, node + m + 1); 317 if(n <= 5 && m <= 10) { 318 bf::solve(); 319 return 0; 320 } 321 if(n <= 5000 && m <= 10000) { 322 bf2::solve(); 323 return 0; 324 } 325 if(largeA <= 30) { 326 bf3::solve(); 327 return 0; 328 } 329 /// lct solve 330 int ans = INF; 331 ufs::init(); 332 for(int i = 1; i <= m; i++) { 333 lct::val[n + i] = node[i].b; 334 } 335 for(int i = 1; i <= m; i++) { 336 int x = node[i].x, y = node[i].y; 337 if(ufs::check(x, y)){ 338 int t = lct::ask(x, y); 339 if(lct::val[t] <= node[i].b) continue; 340 lct::cut(t, node[t - n].x); 341 lct::cut(t, node[t - n].y); 342 lct::link(x, n + i); 343 lct::link(y, n + i); 344 } 345 else { 346 lct::link(x, n + i); 347 lct::link(y, n + i); 348 ufs::merge(x, y); 349 } 350 if(ufs::check(1, n)) { 351 ans = std::min(ans, node[i].a + lct::val[lct::ask(1, n)]); 352 } 353 } 354 if(ans == INF) ans = -1; 355 printf("%d ", ans); 356 return 0; 357 }