并查集

依旧是BZOJ的题集…
做完后翻了翻TB以前的那个专题Word,发现所有题目都有…原来当时就还没有搞完…
然后现在还有一个坑就是可持久化并查集,联赛之后如果没有AFO就补吧er…

简单并查集

[BZOJ 1529] POI2005 ska Piggy banks

[Description]

n个存钱罐,只能用钥匙打开或砸开。每个存钱罐有一把钥匙,放在任意一个存钱罐中,问最少要砸开多少个存钱罐才能打开所有存钱罐。

[Hint]

$n≤10^6$

[Solution]

打了Tarjan缩点统计度为0的点数然后喜闻乐见地MLE了…然而并查集不知道优越到哪里去了…
发现每个点有且仅有一个前驱,所以连通块的形状一定是一个环或者一个环从某点长出一条链…
然后统计连通块个数就可以了…

[BZOJ 2079] POI2079 Guild

[Description]

给出一个n个点m条边的无向图,现在要进行黑白染色,要满足某个点要与自己不同颜色的点相连,问是否能做到。

[Hint]

$n≤2\cdot 10^5,m≤5\cdot 10^5$

[Solution]

傻逼题…
对一个连通块求任意一棵生成树然后分层染色就是合法的方案。
不合法当且仅当存在大小为1的连通块。

[BZOJ 1116] POI2008 CLO

[Description]

给出一个n个点m条边的无向图。现在可以将一些边变成有向边,问可不可以做到每个点有且只有一条有向入边。

[Hint]

$n≤10^5,m≤2\cdot 10^5$

[Solution]

我们发现一个连通块中若存在环整个连通块就可行,依次判断即可。
用并查集尤为方便:另开一个数组记录以某个点为根的并查集存不存在环,若某条边的两个点在同一个并查集中,将这个并查集的根标为true.
最后只用判断是否所有根都为true即可。

[BZOJ 1854] SCOI2010 游戏

[Description]

n个物品,每个物品有两个属性值a,b,分别为1~10000的一个整数。每种物品仅可以发挥出一种属性值。
问最大的x,使得[1,x]所有属性值的物品都存在。

[Hint]

$n≤10^6$

[Solution]

听说能用并查集做…
把属性值定义为点,同一物品的属性a,b看边(a,b),这样建成一个图。
我们需要“为每条边选一个指向,使得被指向的点尽量多”。是不是有点像上一题了呢?但并不尽相同。
若一个连通块存在环,同样还是所有点都能被指向。
考虑树的情况,我们发现可以构造出一种方案任意n-1个点被指向。
因为题意要求尽量小的物品存在,所以我们规定树中值最大的点不被指(同样在并查集中可以实现,开一个数组标记某个元素被不被指,合并两个并查集时将根较小的标记为true,并把它连到另一个根上;若某条边的两个点在同一个并查集中,将这个并查集的根标为true)。
最后$O(n)$判断一下就可以了。

可拆的并查集

其实就是不加路径压缩…

[BZOJ 1016] 最小生成树计数

[Description]

给出一个n个点m条边的带权无向图,相同边权不会超过10个,询问最小生成树个数。

[Hint]

$n≤100,m≤1000$

[Solution]

每种边权的贡献是一定的。统计一下然后DFS.

带权并查集

[BZOJ 1202] 狡猾的商人

[Description]

长度为n的一个序列,有m条信息(a,b,c),表示区间[a,b]的和为c。询问所有信息是否有冲突。

[Hint]

多组数据。$n≤100,m≤1000$.

[Solution]

另开一个数组记录一下与根之间的距离即可(比较容易就不多说了)。

More

码一些之前做过的,都相对简单。

[BZOJ 1050] 旅行

最小瓶颈生成树。

[BZOJ 1015] 星球大战

离线处理。

[BZOJ 2054] 疯狂的馒头

并查集或链表。

[BZOJ 1370] 团伙

设立虚点。

[BZOJ 4195] NOI2015 程序自动分析

NOI竟然有这种题…

Ural1003 奇偶性

虚点。

NOIP2010 关押罪犯

虚点。

NOI2002 银河英雄传说

带权并查集。

NOI2002 食物链

带权并查集或虚点。

POI 代码等式

POI 可爱的猴子

离线处理。

APOI2011 方格染色

好题~