zcmimi's blog

arrow_back并查集共20篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

还是lct维护最小生成树

先按a变排序,然后b边的处理类似WC2006水管局长

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

m \le 5000

数据这么小,直接把边排序一下,然后暴力枚举,用kruskal就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

link\ cut\ tree维护最小生成树

直接在线很难,我们可以离线加边

先把所有边(后来断掉的不算)跑一遍最小生成树

接着每次加边,设加xy,边长为w

先求出xy路径上最长的边

如果比要加的边长,则删掉这条边,加上新边

这样就可以lct维护最小生成树

因为lct不能直接维护点,所以我们可以把边看成点

x\rightarrow边\rightarrow y

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

还是用并查集统计连通块大小

离线处理,按相关性从大到小加边

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

可以用带权并查集维护

s_x表示x到父亲的异或值

当合并的时候

l=l-1

fl,fr分别为l,r的父亲

合并后应该是:s_r \bigoplus s_l = x

\because s_r' = x \bigoplus s_l, s_r' = s_r \bigoplus s_{fr}',

\therefore s_{fr}' = x \bigoplus s_l \bigoplus s_r

我们又看到0 \leq i < 2^{30}

我们可以用hash或map离散化

注意l,r可以为0,所以实际操作时应该++r

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

并查集技巧:记录每个点后面和它不属于同一个集合的第一个点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先用并查集求出所有连通块(相邻且相同颜色的节点)

接着是相邻节点的颜色都不一样的一棵树

最少次数就是树的直径/2了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

把所有路径上的最大值的和 和 所有路径上的最小值的和 分开算

我们按最大值的计算考虑(最小值就是反过来)

我们考虑一个点能贡献多少次

从它的各个子树中拿出来组合

我们可以按权值从小到大的顺序添加节点

这样就只要和当前要添加的节点联通的点都符合要求

这样的话我们可以用并查集来维护连通块大小

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Rainbow-Ride top: 0

用并查集合并联通块,然后背包

2/2
Search
search