Practice - #include <Seter> - using namespace Orz;
Tarjan模板
相当经典的算法。以前都是背模板的,现在打算较深刻地理解一下……
大致思想:遍历到点x时,在栈中的点是有可能与x组成SCC的点。如果x及其子树能够直接访问到的在栈中的DFS序最小的点是x,则x是一个强连通分量在DFS树中的根。每处理完一个根及其子树的信息,就输出此SCC。
NOIp Day1&Day2 Bless
全完了……OI再见,文化课去了。
明天就是NOIp Day1了……
两年的希望……不要坑爹啊……
左偏树模板
左偏树真是个超好写的东西!支持合并,插入,删除最小值三个操作。后两个操作都可以看成第一个操作的拓展,如删除最小值是合并根的两棵子树,插入则直接将元素看作一个左偏树——所以只要写个Merge就可以了!
朱刘算法模板
小黑书上说朱刘算法求的是不定根最小树形图,但是网上找到的资料都说是定根最小树形图……管他呢……
前前后后写了六个小时左右……一开始写每次消掉一个环的DFS,各种2B错误,调了三个小时才好……
然后又改成BFS+拓扑排序的一次消去所有环的方法……这样可以不用记录最小入边的反向边。然后边减小的量用个数组保存起来,这样就不用记录整张图的反向边了。