由于准备再战XCPC, 因此我要开始复健OI!

图论

2-SAT

感觉之前打oi的时候理解的并不透彻啊. 首先,2-SAT算法的本质是以下两个公式:

因此,当我们遇到一个2-CNF的时候,我们会尝试把其中的所有转化为, 得到的会是和原本公式完全等价的新公式.

你可能会有个疑问: 既然,为什么我要在这里把一块加上呢?看上去即使不加也不会出现问题呀. 这个原因我们下面再解释.

得到新的公式后,我们就进行建图,并且的确同一个SCC内的原子公式必须取相同值,从而我们必然需要从后往前取SCC,这就有了三种情况:

  1. 和在同一个SCC里,此时必然无解.
  2. 在里,在里,并且有.此时当然只能选择.
  3. 在里,在里,但是和没有任何依赖关系,此时随便选一个.

等一下,(3)这里竟然可以随便选一个?那我立刻就想到一种情况啊:比如,此时选了后,可能还有一些原子命题没得到赋值(比如,的大小可能小于的大小,从而导致漏了一些原子命题),所以我们又不得不选,可是选了后又不得不选,这一下子不就出矛盾了么!

为了理解为什么这里不会出矛盾,我们来看一下此时和到底是怎样的关系:

我们重新回到刚才那个问题:为什么添加后还要添加呢?这实际上起到的作用是(我们用表示到有一条路径.):如果,则必然也有.

如果,必然说明,并且根据我们上面说的,这导出了并且.这意味着.也就是说,这两个SCC必然是精确对应着彼此的,选择它们哪个后,另一个都完全被否定了.我们不妨用来表示这种关系.

然而这还是有问题,那为什么不可能出现,然后我们被迫选了的可能性呢?这其实是因为如果以及,必然意味着以及,也就是说必定在和之前,因此这个就没有任何道理被选择了.

现在应该容易给出为何只要和不在同一个SCC,就一定有解的理解了:这个缩点后的图确实比较特殊.这个图一定有个结点,其中每个结点都存在一个与之对应,我们最后一定会从这个节点中选出个结点(每一对都要二选一),使得不存在一个"被选择的点"指向一个"未被选择的点".

我们最后想说明在新得到的图中,一定存在一个"后缀子图"(这名字是我自己编的,但是应该可以理解是什么意思?),使得其恰好完成了上面的选择.为此我们直接倒着拓扑排序开始扩张,如果遇到一个可以加入的SCC就加入.这样做一定可以取出个SCC吗?假设和都没被加入,当前拓扑排序最靠后的位置是,这说明:

  1. 已经被加入了,因此不能被加入.
  2. 的排序在之前,意味着.

可是这意味着,因此应该拓扑排序在之前,因此它应该早就被加入了!

连通分量全家桶

先来看有向图的强连通分量, 这个是在干什么呢? 其实它的目标真的就是缩点.

  1. 首先, 我们对图进行dfs并编号dfn, 我们知道如果是整棵树中dfn最小的那个, 那整个强连通分量一定在以它为根的子树内, 事实上它们还一定是子树中连续的一块.
  2. 因此, 考虑任何一条遍历的链, 如果链上存在两个点在同一个强连通分量中, 它们中间的所有点必定也在一起. 如果用栈维护这个结构, 只需要知道到当前这条链最前面那个点是谁, 这就是low的作用, 也是为什么low只处理在stack内的dfn.
  3. 由于这个可以一路往上跳, 因此写成low[x]=std::min(low[x],dfn[v])还是low[x]=std::min(low[x],low[v])并不影响正确性

再来看无向图的边双连通, 很好用的性质是边双等价于存在两条边不相交的路径, 原因是边双连通意味着最小割, 从而最大流. 这还可以导出边双的传递性. 事实上, 边双性质非常之好, 它的写法几乎和有向图强连通分量没什么区别.

但是点双性质很差! 原因就在于点双不满足传递性. 不过至少它还在dfs树上是连续的一段. 所以还可以用上述方式求解. 可因为它不满足传递性, 所以它的写法是唯一固定的.

事实上, 对于已经在栈里面的点来说, low[x]=std::min(low[x],dfn[v])其实才是真正自然的写法: 如果你认为low[x]=std::min(low[x],low[v])是自然的写法, 可能是因为你给了low一个更确切的几何意义: 你认为它就代表着能走到的编号最小的点. 但实际上low的功能只是标记一下这里还能不能往上走. 即使按照"能走到的编号最小的点"来理解, 你发现它也是不对的, 因为只扫了一遍, 这个low根本没收敛到这个"解释"上. 如果再做一遍low[x]=std::min(low[x],low[v])的话这个low的值还会变化呢.

顺便一提点双也满足存在两条(除了起点和终点以外)点不相交的路径, 原因是你可以把一个点拆成和, 然后继续用网络流.

不过点双还是有一些好的性质的: 对于一个点双中的两点, 它们之间简单路径的并集恰好完全等于这个点双.

首先, 对于简单路径, 如果你从这个点双走出去了(一定经过某个割点), 再想走回来是不可能的(必须再经过这个割点). 所以我们只需要证明对于点双中的任意三个点, 都存在一条的路径.

这个的证明竟然也要途径最大流最小割定理: 考虑中间拆点, 从往流, 看流量是否能到. 我们只需要证明这个导出图的最小割就行. 而由于这是个点双, 最小割显然.

有没有更好的证明办法呢? 实际上我们有耳分解: 任何一个点双连通分量, 都可以通过在一个初始简单环上"加耳"得到: 选择图上两个点, 并加一链新点连接.

耳分解如何证明呢? 考虑一个点双, 我们任取其中的一个简单环, 并对加耳, 但要求总是的子图. 这么做下去, 由于的子图数量有限, 存在一个是这种做法能生成的边数最多的子图, 我们来证明: 如果点数相同但边数不同则直接加边就好了. 不然, 由于原图连通, 一定存在着一条边连接和, 设这条边为. 可是由于点双连通, 删掉后, 一定还存在一条到的路径. 这样就可以继续加耳.

用耳分解就可以更好地证明上面那个结论: 数学归纳, 假设第次加耳后得到的图是, 假设的图都满足上面那个性质, 则新加耳后讨论一下在里面的两个点之间的简单路径(可以通过它们连接的那两个点), 以及分别在和在里面的两个点之间的简单路径, 就可以了.

顺便一提边双也可以耳分解, 只是边双允许加耳的两个点相同.

数据结构

莫队

重新学了一下莫队-回滚莫队-二次离线莫队, 总结一下就是:

  1. 当你发现你可以快速扩大或者缩小区间并且计算答案的时候, 进行莫队.
  2. 当你发现可以快速扩大区间, 但很难缩小区间的时候, 进行回滚莫队.
  3. 当你发现扩大区间和缩小区间都带一个额外的复杂度, 尝试二次离线莫队.