并查集真是一个判断连通的好东西！
连通性用并查集来搞。
把每一条边按照 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 { 15 int x, y, a, b; 16 }e[N]; 17 18 inline int read() 19 { 20 int x = 0, f = 1; 21 char ch = getchar(); 22 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 23 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 24 return x * f; 25 } 26 27 inline bool cmp(node x, node y) 28 { 29 return x.a < y.a; 30 } 31 32 inline int getf(int x) 33 { 34 return x == fa[x] ? x : fa[x] = getf(fa[x]); 35 } 36 37 inline void update(int x) 38 { 39 if(x) 40 { 41 mx[x] = x; 42 if(son[x][0] && val[mx[son[x][0]]] > val[mx[x]]) mx[x] = mx[son[x][0]]; 43 if(son[x][1] && val[mx[son[x][1]]] > val[mx[x]]) mx[x] = mx[son[x][1]]; 44 } 45 } 46 47 inline void pushdown(int x) 48 { 49 if(x && rev[x]) 50 { 51 swap(son[x][0], son[x][1]); 52 if(son[x][0]) rev[son[x][0]] ^= 1; 53 if(son[x][1]) rev[son[x][1]] ^= 1; 54 rev[x] = 0; 55 } 56 } 57 58 inline void rotate(int x) 59 { 60 int old = f[x], oldf = f[old], wh = get(x); 61 62 if(!isroot(old)) 63 son[oldf][get(old)] = x; 64 f[x] = oldf; 65 66 son[old][wh] = son[x][wh ^ 1]; 67 f[son[old][wh]] = old; 68 69 son[x][wh ^ 1] = old; 70 f[old] = x; 71 72 update(old); 73 update(x); 74 } 75 76 inline void splay(int x) 77 { 78 int i, fat, t = 0; 79 s[++t] = x; 80 for(i = x; !isroot(i); i = f[i]) s[++t] = f[i]; 81 for(i = t; i; i--) pushdown(s[i]); 82 for(; !isroot(x); rotate(x)) 83 if(!isroot(fat = f[x])) 84 rotate(get(x) ^ get(fat) ? x : fat); 85 } 86 87 inline void access(int x) 88 { 89 for(int t = 0; x; t = x, x = f[x]) splay(x), son[x][1] = t, update(x); 90 } 91 92 inline void reverse(int x) 93 { 94 access(x); 95 splay(x); 96 rev[x] ^= 1; 97 } 98 99 inline void cut(int x, int y) 100 { 101 reverse(x); 102 access(y); 103 splay(y); 104 son[y][0] = f[x] = 0; 105 update(y); 106 } 107 108 inline void link(int x, int y) 109 { 110 reverse(x); 111 f[x] = y; 112 access(x); 113 } 114 115 inline int find(int x) 116 { 117 access(x); 118 splay(x); 119 while(son[x][0]) x = son[x][0]; 120 return x; 121 } 122 123 inline int query(int x, int y) 124 { 125 reverse(x); 126 access(y); 127 splay(y); 128 return mx[y]; 129 } 130 131 int main() 132 { 133 int i, j, k, x, y, a, b, t, fx, fy; 134 n = read(); 135 m = read(); 136 for(i = 1; i <= n; i++) fa[i] = i; 137 for(i = 1; i <= m; i++) 138 { 139 e[i].x = read(); 140 e[i].y = read(); 141 e[i].a = read(); 142 e[i].b = read(); 143 x = getf(e[i].x); 144 y = getf(e[i].y); 145 if(x ^ y) fa[x] = y; 146 } 147 if(getf(1) ^ getf(n)) 148 { 149 puts("-1"); 150 return 0; 151 } 152 std::sort(e + 1, e + m + 1, cmp); 153 for(i = 1; i <= m; i++) 154 { 155 mx[i + n] = i + n; 156 val[i + n] = e[i].b; 157 } 158 for(i = 1; i <= n; i++) fa[i] = i; 159 for(i = 1; i <= m; i++) 160 { 161 x = e[i].x; 162 y = e[i].y; 163 fx = getf(x); 164 fy = getf(y); 165 if(fx ^ fy) 166 { 167 link(x, i + n); 168 link(y, i + n); 169 fa[fx] = fy; 170 } 171 else 172 { 173 t = query(x, y); 174 if(e[i].b < val[t]) 175 { 176 cut(e[t - n].x, t); 177 cut(e[t - n].y, t); 178 link(x, i + n); 179 link(y, i + n); 180 } 181 } 182 if(getf(1) == getf(n)) ans = min(ans, e[i].a + val[query(1, n)]); 183 } 184 printf("%d ", ans); 185 return 0; 186 }
排序很关键！
如果做不出来，先排序试试。