【BZOJ1023】【SHOI2008】仙人掌图

我只是来学元芳树的

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

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

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

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

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

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

 

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

说点什么

1 评论 在 "【BZOJ1023】【SHOI2008】仙人掌图"

提醒
排序:   最新 | 最旧 | 得票最多
成员

orz

wpDiscuz