mcs – Tgotp-Blog

P1352 没有上司的舞会

思路:弦图

算法:mcs

具体:你会发现其实树也是弦图,它没有环,也是无向图,所以可以尝试搞一下,我是对于val这里修改了一下,其余的套模板,参考cdq的弦图与区间图ppt。对于这道题,因为val可能为负值,所以判断一下就ok。

ps: 与某位大佬无意间说起的一题,说实在我没有想到[......]

Read more

bzoj1006 P3196 [HNOI2008]神奇的国度

思路:弦图

算法:mcs,邻接表

具体实现:逆序寻找完美消除序列,然后染成能染的最小颜色,证明参见cdq的弦图与区间课件。

c++代码: