严格次小生成树

发现一个性质,严格次小生成树和最小生成树一定只相差了一条边。 依次枚举加入的边即可。维护次大值比较麻烦。

阅读更多

跳树

跳树

考虑将3种操作转化为二进制上的左移 右移 往上跳。

在这里用到了虚拟的思想(并非虚树),假装这个树高度无限。然后线段树即可。

阅读更多

2-SAT

$\rm 2-SAT$ 描述的是这样一类问题:

2020-08-27_18-38.png

算法概论

通常采用图论建模,然后 Tarjan 解决.

考虑拆点,将一个变量 $x$ 拆成 $x_1,x_2$,分别对应真假两个状态

如果选了状态$x_1$后,必须要选状态$y_1$,那么我们就连一条 $(x_1,y_1)$的有向边.

阅读更多