基环树&仙人掌小结

前言

基环树和仙人掌都是特殊的图,都有一些类似于树的性质,可以根据这些性质来解决问题。

基环树

概述

基环树就是一张n个点用n条边连起来的树。我们可以把它想象成一个环,环上每一个点都是一棵树的根。
基环树的基本做法都是要先找到环,然后一般有两种处理方法:
一是枚举环上断边把基环树变成树,然后按树的方法做。这种方法在环很大的情况下效率较低,不是很常见。
第二种是将环和树分类来做。比较常见的基环树题都是先对环上每个节点对应的树进行处理,然后对环使用一些数据结构进行处理。

例题

[洛谷P2607][ZJOI2008]骑士(较简单的题)
[洛谷P4381][IOI2008]Island(较简单的题)
[洛谷P2081][NOI2012]迷失游乐园(有点复杂的题)
[洛谷P4949]最短距离(有点复杂的题)

仙人掌

概述

仙人掌分为两类:点仙人掌和边仙人掌。点仙人掌的定义为一个任意一个点不同时处于两个环中的简单无向连通图,边仙人掌的定义为一个任意一条边不同时处于两个环中的简单无向连通图。基环树也可以看做特殊的仙人掌。
不管是点仙人掌还是边仙人掌个人觉得做法都类似。仙人掌DP的话只要处理好环与遍历顺序的关系即可。但是有一种在仙人掌问题中适用范围非常广的模型:圆方树(本人是逢仙人掌必圆方树的)。

圆方树

我们将原先的点称为圆点,每个点双联通分量建一个点,称为方点。删除原先所有圆点之间的连边,然后对于每一个方点,对其所对点双中的每一个圆点连一条边。这个时候我们可以证明得到的是一棵树。举个例子,比如说这个边仙人掌:

圆方树:

我们在建完圆方树之后只需要按树遍历,然后将圆点和方点分开来做即可。也经常可以看到在圆方树上套树上倍增,树链剖分之类的东西。

例题

仙人掌的题目较多,一些比较变态的题我也没写过(如动态仙人掌)。这里给出较简单的题。
[bzoj4316]小C的独立集
[洛谷P4410][HNOI2009]无归岛
[bzoj2125]最短路

毒瘤题

这些变态仙人掌题这里先放一下。。。我都没写过
[uoj#23]跳蚤国王下江南
[bzoj3464]动态仙人掌I
[bzoj3465]动态仙人掌II
[bzoj3466]动态仙人掌III

Tagged with:

发表评论