【BZOJ1023】【SHOI2008】仙人掌图

我只是来学元芳树的

调了一天 心好累 不想写题解了

大概就是对仙人掌求一遍边双,对于每个环把最靠近根节点的提出来做这个环的根,并新建一个方点表示这个环。删除这个环上原来的边,从环根向方点连一条边,再从方点向其它点连边。这样新构出来的就是一颗树,称为圆方树。

那么再处理这棵树即可。圆点和方点分开考虑。

(所以我又顺便学会了怎么求边双)

dfs时碰到下一个点的\(low\)值就等于该点\(dfn\)值则栈中一直到这个点的所有点构成一个边双。

如果下一个点的\(low\)值大于该点\(dfn\)也要弹出栈顶。

 

对于方点的处理,只要把环倍长一下,只用前\(len/2\)个元素更新。用单调队列处理即可。

Subscribe
提醒
1 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
LCF
3 年 之前

orz