边带权并查集 学习笔记 & 洛谷P1196 [NOI2002] 银河英雄传说 题解

花了2h总算把边带权并查集整明白了qaq
1.边带权并查集的用途
众所周知，并查集擅长维护与可传递关系有关的信息。然而我们有时会发现并查集所维护的信息不够用，这时“边带权并查集”就应运而生了。
2.例题与思路
这里通过例题 洛谷P1196 [NOI2002] 银河英雄传说 来介绍边带权并查集的思想。题面请点击链接查看。
2.1.暴力
拿到这道题我的第一想法就是用链表模拟。对于两艘在同一列的战舰，只需知道它们到队首的距离(设距离分别为 /(dis_1/) 和 /(dis_2/))就可以知道它们之间的距离(为 /(|dis_1-dis_2|+1/))。对于每艘战舰，记录它前面的战舰是哪一艘，查询时通过暴力往前跳来查询 /(dis_1/) 和 /(dis_2/)，合并时暴力合并。这样显然会超时，于是我们考虑优化。
2.2.优化
可以考虑使用路径压缩的方式进行优化。对于这样一个链表:

它等价于：

同时这样查询时要跳的步数就少很多。这其实就是路径压缩。
同时我们还需要记录每一列的战舰数，在合并

边带权并查集 学习笔记 & 洛谷P1196 [NOI2002] 银河英雄传说 题解最先出现在Python成神之路。