首页 > 代码库 > [BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）
[BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）
传送门
WC这个题真是丧心病狂啊，就是想学习一下怎么处理边权，给我来了这么一个破题！
ORZ hzwer 临摹黄学长代码233 但还是复杂的一匹
理一下思路吧
题目大意：给定一个无向图，多次删除图中的某一条边，求两点间路径最大值的最小值
求两点间的路径最大值的最小值的话，可以求最小生成树，那么这个值就是最小生成树上两点间路径上的最大值
但是题目要求是删除边，LCT维护最小生成树不支持删边操作，那么就离线处理，倒着加边，用LCT维护。
就是这个离线处理是最恶心的。
来说说如何处理边权，把边也抽象成点，那么这个点就和原来边所连的两个点相连，其中边抽象成的点点权为边权，所连接的两个点点权为 0
给边从小到大排序，那么边所抽象成的点的序号即为 边的序号 + n （n 为原来点的个数）
然后再将边按照它所连的两个点为关键字排序，二分查找确定所删除的边的序号。
再按照从小到大的顺序再排回来，跑 kruskal，依次添加没有被删除的边
最后从后往前处理询问，添加一条边的时候先判断两端点是否连通（当然此题不必，因为题目中说：任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。。所以肯定连通）
然后找出两点间路径边权的最大的，判断最大的边权是否大于要加入的边的边权，如果大于，就删除这条边，连接新边，否则就不加入（维护最小生成树）
具体细节看代码
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define N 1500005 6 #define get(x) (son[f[x]][1] == (x)) 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, Q, tot; 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, z, id; 16 bool d; 17 }e[N]; 18 19 struct ask 20 { 21 int f, x, y, ans, id; 22 }q[N]; 23 24 inline int read() 25 { 26 int x = 0, f = 1; 27 char ch = getchar(); 28 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 29 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 30 return x * f; 31 } 32 33 inline bool cmp1(node x, node y) 34 { 35 return x.z < y.z; 36 } 37 38 inline bool cmp2(node x, node y) 39 { 40 return x.x < y.x || (x.x == y.x && x.y < y.y); 41 } 42 43 inline bool cmp3(node x, node y) 44 { 45 return x.id < y.id; 46 } 47 48 inline int getf(int x) 49 { 50 return x == fa[x] ? x : fa[x] = getf(fa[x]); 51 } 52 53 inline int find(int x, int y) 54 { 55 int l = 1, r = m, mid; 56 while(l <= r) 57 { 58 mid = (l + r) >> 1; 59 if(e[mid].x < x || (e[mid].x == x && e[mid].y < y)) l = mid + 1; 60 else if(e[mid].x == x && e[mid].y == y) return mid; 61 else r = mid - 1; 62 } 63 } 64 65 inline void update(int x) 66 { 67 if(x) 68 { 69 mx[x] = x; 70 if(son[x][0] && val[mx[son[x][0]]] > val[mx[x]]) mx[x] = mx[son[x][0]]; 71 if(son[x][1] && val[mx[son[x][1]]] > val[mx[x]]) mx[x] = mx[son[x][1]]; 72 } 73 } 74 75 inline void pushdown(int x) 76 { 77 if(x && rev[x]) 78 { 79 swap(son[x][0], son[x][1]); 80 if(son[x][0]) rev[son[x][0]] ^= 1; 81 if(son[x][1]) rev[son[x][1]] ^= 1; 82 rev[x] = 0; 83 } 84 } 85 86 inline void rotate(int x) 87 { 88 int old = f[x], oldf = f[old], wh = get(x); 89 90 if(!isroot(old)) 91 son[oldf][get(old)] = x; 92 f[x] = oldf; 93 94 son[old][wh] = son[x][wh ^ 1]; 95 f[son[old][wh]] = old; 96 97 son[x][wh ^ 1] = old; 98 f[old] = x; 99 100 update(old);101 update(x);102 }103 104 inline void splay(int x)105 {106 int i, fat, t = 0;107 s[++t] = x;108 for(i = x; !isroot(i); i = f[i]) s[++t] = f[i];109 for(i = t; i; i--) pushdown(s[i]);110 for(; !isroot(x); rotate(x))111 if(!isroot(fat = f[x]))112 rotate(get(x) ^ get(fat) ? x : fat);113 }114 115 inline void access(int x)116 {117 for(int t = 0; x; t = x, x = f[x]) splay(x), son[x][1] = t, update(x);118 }119 120 inline void reverse(int x)121 {122 access(x);123 splay(x);124 rev[x] ^= 1;125 }126 127 inline void cut(int x, int y)128 {129 reverse(x);130 access(y);131 splay(y);132 son[y][0] = f[x] = 0;133 update(y);134 }135 136 inline void link(int x, int y)137 {138 reverse(x);139 f[x] = y;140 access(x);141 }142 143 inline int query(int x, int y)144 {145 reverse(x);146 access(y);147 splay(y);148 return mx[y];149 }150 151 int main()152 {153 int i, j, k, t, x, y, fx, fy;154 n = read();155 m = read();156 Q = read();157 for(i = 1; i <= n; i++) fa[i] = i;158 for(i = 1; i <= m; i++)159 {160 e[i].x = read();161 e[i].y = read();162 e[i].z = read();163 if(e[i].x > e[i].y) swap(e[i].x, e[i].y);164 }165 std::sort(e + 1, e + m + 1, cmp1);166 for(i = 1; i <= m; i++)167 {168 e[i].id = i;169 val[n + i] = e[i].z;170 mx[n + i] = n + i;171 }172 std::sort(e + 1, e + m + 1, cmp2);173 for(i = 1; i <= Q; i++)174 {175 q[i].f = read();176 q[i].x = read();177 q[i].y = read();178 if(q[i].x > q[i].y) swap(q[i].x, q[i].y);179 if(q[i].f == 2)180 {181 t = find(q[i].x, q[i].y);182 e[t].d = 1;183 q[i].id = e[t].id;184 }185 }186 std::sort(e + 1, e + m + 1, cmp3);187 for(i = 1; i <= m; i++)188 if(!e[i].d)189 {190 x = e[i].x;191 y = e[i].y;192 fx = getf(x);193 fy = getf(y);194 if(fx ^ fy)195 {196 fa[fx] = fy;197 link(x, i + n);198 link(y, i + n);199 tot++;200 if(tot == n - 1) break;201 }202 }203 for(i = Q; i; i--)204 {205 if(q[i].f == 1) q[i].ans = val[query(q[i].x, q[i].y)];206 else207 {208 x = q[i].x;209 y = q[i].y;210 k = q[i].id;211 t = query(x, y);212 if(e[k].z < val[t])213 {214 cut(e[t - n].x, t);215 cut(e[t - n].y, t);216 link(x, k + n);217 link(y, k + n);218 }219 }220 }221 for(i = 1; i <= Q; i++)222 if(q[i].f == 1)223 printf("%d\n", q[i].ans);224 return 0;225 }
[BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。