[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 e[N]; 18 19 struct ask 20 q[N]; 23 24 inline int read() 25 32 33 inline bool cmp1(node x, node y) 34 37 38 inline bool cmp2(node x, node y) 39 42 43 inline bool cmp3(node x, node y) 44 47 48 inline int getf(int x) 49 52 53 inline int find(int x, int y) 54 } 64 65 inline void update(int x) 66 73 } 74 75 inline void pushdown(int x) 76 84 } 85 86 inline void rotate(int x) 87 103 104 inline void splay(int x) 105 114 115 inline void access(int x) 116 119 120 inline void reverse(int x) 121 126 127 inline void cut(int x, int y) 128 135 136 inline void link(int x, int y) 137 142 143 inline int query(int x, int y) 144 150 151 int main() 152 165 std::sort(e + 1, e + m + 1, cmp1); 166 for(i = 1; i <= m; i++) 167 172 std::sort(e + 1, e + m + 1, cmp2); 173 for(i = 1; i <= Q; i++) 174 185 } 186 std::sort(e + 1, e + m + 1, cmp3); 187 for(i = 1; i <= m; i++) 188 if(!e[i].d) 189 202 } 203 for(i = Q; i; i) 204 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 }
View Code

上一篇：[luoguP2486] [SDOI2011]染色（树链剖分）

下一篇：[POJ3728]The merchant（tanrjan_lca + DP）

---

最小生成树 kruskal LCT