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+拓扑排序的一次消去所有环的方法……这样可以不用记录最小入边的反向边。然后边减小的量用个数组保存起来,这样就不用记录整张图的反向边了。

继续阅读




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee