标签：并查集

题目链接：P2024 [NOI2001] 食物链 思路 本题可以使用“扩展域并查集”的方法来解决，即把每个节点拆成三种角色（本体、吃的、被吃的）来模拟三种关系。也可以使用“带权并查集”方法，通过设置每个节点到其父节点的相对关系来处理三种状态...

赞(0)xiaoeyv2025-06-20C++ 阅读(15)

题目链接：P1892 [BalticOI 2003] 团伙 思路 除了并查集外，还要记录每个人之间的关系，典型的扩展域并查集模板题。 代码 写的时候用了秩优化，能优化一些效率。 // // Created by xiaoeyv on 202...

赞(0)xiaoeyv2025-06-20C++ 阅读(30)

题目链接：P2820 局域网 – 洛谷 题目简述 去除 $k$ 个边中的最大回路边。 思路 在输入的时候统计权重总和，减去最小生成树的总和。 这道题用简单数组实现 Prim，复杂度是 $O(n^2)$； 用堆优化的 Prim 是...

赞(0)xiaoeyv2025-06-19C++ 阅读(27)

题目链接：P2078 朋友 – 洛谷 思路 这道题思路很简单，建立A公司和B公司的并查集，遍历小明认识的人ans1和小红认识的人ansB，然后输出min(ansA, ansB)即可 代码 // // Created by xia...

赞(1)xiaoeyv2025-06-18C++ 阅读(22)