为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000
题解
LCT＋Kruskal
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <cctype> 6 7 inline void read(int & x) 8 { 9 x = 0; 10 int k = 1; 11 char c = getchar(); 12 while (!isdigit(c)) 13 if (c == ‘-‘) c = getchar(), k = -1; 14 else c = getchar(); 15 while (isdigit(c)) 16 x = (x << 1) + (x << 3) + (c ^ 48), 17 c = getchar(); 18 x *= k; 19 } 20 21 const int N = 505050, inf = 2147483645; 22 int n, m, tot, rt = 0, x, y, A, B, z, top = 0, ans = inf, stk_top = 0, cur; 23 int faz[N], siz[N], sma[N], tag[N], val[N], cnt[N], son[N][2], fa[N], stk[N], L[N], R[N]; 24 25 inline int min(const int &a, const int &b) 26 { 27 return a > b ? b : a; 28 } 29 30 inline void Swap(int &a, int &b) 31 { 32 a ^= b, b ^= a, a ^= b; 33 } 34 35 inline int Root(int u) 36 { 37 return son[faz[u]][0] != u && son[faz[u]][1] != u; 38 } 39 40 inline int Getson(int u) 41 { 42 return son[faz[u]][1] == u; 43 } 44 45 inline void Pushup(int u) 46 { 47 sma[u] = u; 48 if (val[sma[u]] < val[sma[son[u][0]]]) sma[u] = sma[son[u][0]]; 49 if (val[sma[u]] < val[sma[son[u][1]]]) sma[u] = sma[son[u][1]]; 50 } 51 52 inline void Pushdown(int u) 53 { 54 if (!tag[u]) return; 55 tag[son[u][0]] ^= 1, 56 tag[son[u][1]] ^= 1, 57 Swap(son[u][0], son[u][1]); 58 tag[u] = 0; 59 } 60 61 inline int New(int x) 62 { 63 int u = ++tot; 64 siz[u] = cnt[u] = 1, 65 son[u][0] = tag[u] = 66 faz[u] = son[u][1] = 0, 67 val[u] = x, sma[u] = u; 68 return u; 69 } 70 71 inline void Ratate(int u) 72 { 73 int y = faz[u], z = faz[y], ch = Getson(u), b = son[u][ch ^ 1]; 74 Pushdown(y), Pushdown(u); 75 if (!Root(y)) son[z][Getson(y)] = u; 76 son[u][ch ^ 1] = y, son[y][ch] = b, 77 faz[u] = z, faz[b] = y, faz[y] = u; 78 Pushup(y), Pushup(u); 79 } 80 81 inline void Splay(int u) 82 { 83 int cur = u; 84 stk[stk_top = 1] = u; 85 while (!Root(u)) stk[++stk_top] = u = faz[u]; 86 while (stk_top) Pushdown(stk[stk_top--]); 87 while (!Root(cur)) 88 { 89 if (!Root(faz[cur])) 90 if (Getson(cur) == Getson(faz[cur])) Ratate(faz[cur]); 91 else Ratate(cur); 92 Ratate(cur); 93 } 94 } 95 96 inline void Access(int u) 97 { 98 for (int ch = 0; u; u = faz[ch = u]) 99 Splay(u), son[u][1] = ch, Pushup(u); 100 } 101 102 inline void Mkrt(int u) 103 { 104 Access(u), Splay(u), tag[u] ^= 1; 105 } 106 107 inline void Split(int x, int y) 108 { 109 Mkrt(x), Access(y), Splay(y); 110 } 111 112 inline void Link(int a, int b) 113 { 114 Mkrt(a), faz[a] = b; 115 } 116 117 inline void Cut(int a, int b) 118 { 119 Split(a, b); 120 if (son[b][0] != a || faz[a] != b) return; 121 faz[a] = 0, son[b][0] = 0; 122 Pushup(b); 123 } 124 125 inline int Get(int a, int b) 126 { 127 Split(b, a); 128 return sma[a]; 129 } 130 131 struct Edge 132 { 133 int u, v, a, b; 134 bool operator < (const Edge &B) const 135 { return a < B.a; } 136 }e[505050]; 137 138 int Find(int u) 139 { 140 return fa[u] == u ? u : fa[u] = Find(fa[u]); 141 } 142 143 inline void Uni(int a, int b) 144 { 145 int r1 = Find(a), 146 r2 = Find(b); 147 if (r1 == r2) return; 148 fa[r1] = r2; 149 } 150 151 inline bool Tgt(int a, int b) 152 { 153 int r1 = Find(a), 154 r2 = Find(b); 155 if (r1 == r2) return true; 156 return false; 157 } 158 159 signed main() 160 { 161 // freopen("a.in", "r", stdin); 162 // freopen("a.out", "w", stdout); 163 read(n), read(m); 164 for (int i = 1; i <= n; ++i) 165 fa[i] = i; 166 for (int i = 1; i <= m; ++i) 167 read(e[i].u), read(e[i].v), 168 read(e[i].a), read(e[i].b); 169 // puts(""); 170 std::sort(e + 1, e + m + 1); 171 for (int i = 1; i <= m; ++i) 172 { 173 if (Tgt(e[i].u, e[i].v)) 174 { 175 if (val[z = Get(e[i].u, e[i].v)] > e[i].b) 176 Cut(e[z - n].u, z), 177 Cut(z, e[z - n].v); 178 else 179 {if (Tgt(1, n)) 180 ans = min(ans, val[Get(1, n)] + e[i].a); 181 continue; 182 } 183 } 184 else Uni(e[i].u, e[i].v); 185 val[n + i] = e[i].b, 186 sma[n + i] = n + i, 187 Link(e[i].u, n + i), 188 Link(n + i, e[i].v); 189 if (Tgt(1, n)) 190 ans = min(ans, val[Get(1, n)] + e[i].a); 191 } 192 if (ans == inf) puts("-1"); 193 else printf("%d\n", ans); 194 return 0; 195 }
原文：https://www.cnblogs.com/yanyiming10243247/p/10057762.html