高度由习惯堆积

分类 数据结构:并查集 下的文章

Hnoi2010 City 城市建设

题目PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定...
February 17, 2019

POJ1417 True Liars(并查集)

题目有一群好人和一群坏人,好人永远说真话,坏人永远说假话。现给出一组话,问能否唯一确定每个人是好人还是坏人。样例输入: 2 1 1 1 2 no 2 1 no 3 2 1 1 1 yes 2 2 yes 3 3 yes 2 2 1 1 2 yes 2 3 no 5 4 3 1 2 yes 1 3 no 4 5 yes 5 6 yes 6 7 no 0 0 0
February 17, 2019

POJ1182 食物链(经典带权并查集 扩展域)

题目动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示X和Y是同类。 第二种说法是"2 X Y",表示X吃Y。 此人对N个动物,用上述两种说法,一句接一句地说出K句话...
February 17, 2019

HDU4424 Conquer a New Region(并查集)

题目给定一棵无根树,求以树上某一点为根,使得这个点到其他点路径上的边权最小值之和最大。思路很容易想到使用类克鲁斯卡尔的算法,将边从大到小进行排序,之后利用并查集维护,则通过某条边连接起来的两个集合,他们之间的点的路径的最小值就是此边。但信息的维护就非常棘手了,一开始想到的是带权并查集维护每一个点的答案,但是它貌似又不满足带权并查集的性质(disr2==0,信息不会被重复更新到),因此卡了一万...