bzoj 4690: Never Wait for Weights 带权并查集

好久不写,相对关系又维护的一团糟。。QwQ。。。还是我太菜了。

不过这题倒是真真切切的裸题

bzoj 4195: [Noi2015]程序自动分析 离散化 并查集

真TMD被自己蠢哭了!!!!!!!

离线一下,暴力先把相等的用并查集连起来,然后在判一遍不等就好了嘛!!!!!

干嘛脑子抽了在那在线搞了半天。。。mdzz。。。。

1196: [HNOI2006]公路修建问题 二分

我可能学了假的语文。看不懂题面。

但是还是推测出了题意,只要二分一下最大的边多大,然后暴力并查集判断就好了。quq

ACM 训练 POJ 3522 Slim Span 并查集

给你一幅无向图,让你选择一些边,构成一颗树。使得树上的max边和min边的差值最小。

把边排序,然后m^2暴力即可。先枚举最小边,然后依次加入边直至图联通,更新最大值。联通用并查集维护。

省选模板-数据结构-带权并查集

省选模板-数据结构-并查集

bzoj 3674: 可持久化并查集加强版

这题真是加强版……原版数据是随机的吧。。加不加启发式合并跑得一样快。。。。。。。。然后自己启发式写跪了没发现。这题一直TLE。检查了半天,交了满页TLE和MLE。。。。然后发现是启发式合并写跪了。

bzoj 3673: 可持久化并查集 by zky

大概就是用可持久化线段树来维护fa和siz数组,然后舍弃路径压缩即可。

开始犯了一些问题,什么变量名写错,最致命的是,我没有考虑到,一旦因为元素已在同一集合,而放弃merge,则会使最新版本成为一颗空的树,显然是不对的,需要特判一下。
[crayon-5c11b38c6e5e71497410[……]

Read more

POJ1948 Navigation Nightmare 带权并查集

简单说就并查集在维护联通性的同时维护一下相对位置即可。维护在水平方向和在竖直方向的相对位置。

 

bzoj 1050: [HAOI2006]旅行comf 枚举 并查集

我们考虑,我们按照边权排序,枚举最大值。然后我们依次加入每条边,直到s,t相连,那么当前的边就是最小值,就可以来更新答案了。

犯了些精度问题。int相除与double比较没(double)WA了一段时间。。