【BZOJ1023】【SHOI2008】仙人掌图

我只是来学元芳树的

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

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

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

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

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

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

 

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

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

orz