P10058 [CCO2022] Phone Plans 题解

Perta · 2024-01-08 20:24:51 · 题解

若两张图点集的交集为空，则分别 kruskal 后双指针即可。

若交集不为空，当前双指针中对应的两张图所保留的点对需要减去重复的。假设连通块有编号，设 T_{i,j} 为既在第一个图中的 i 号连通块，又在第二个图中的 j 号连通块的点数，则重复的点对为 \sum\frac{T_{i,j}(T_{i,j}-1)}{2}。

那么一张图并查集合并，另一张图并查集撤销。注意这个时候需要开个 vector 存每个连通块内的点用于修改 T_{i,j} 与撤销并查集，启发式合并/分裂即可。对于连通块的编号，将其当做并查集的根节点，使用 hash_table / unordered_map 更为方便。

难看的 Code