描述
一些布尔变量组成若干二元简单析取式,求使得这些简单析取式全部为真的赋值方案。
分析
要不我们先建个图?
一个布尔变量有真假两种情况。所以我们令点 $u_i$ 代表第 i 个变量为真,点$u’_i$ 代表第 i 个变量为假。
然后我们搞一点事情。考虑一个点 $u’_i\in V$ ,即 $b_i=0$,要想 $b_i\vee b_j$ 为真,必须有$b_j=1$ 即 $u_j\in S$。
也就是:
……那我们顺手连个边好了。
记一个简单析取式为两个有序二元对,就这样连边:
$\forall (b_i,b_j)\rightarrow (u’_i,u_j) \in E$
现在我们有一个完整的图 $G$ 了。
那么一个合法解就是图 $G$ 的一个点集。
可行性
随便选一个点,把它加入解集,为了使原式成立,那么它能到达的所有点也应该加入解集。这是我们刚刚讨论过的。
对于一个强连通分量,如果我们把其中任意一个点加入解集,那么整个分量都会在解集中。
这是捆绑销售,不能只要一个点。
所以如果 $u_i,u’_i$ 在同一个强连通分量中,那么gg,一个变量不能又真又假。
如果不存在这种情况,我们就可以缩点得到 DAG 。由于无法导出矛盾,所以一定可以得到一个解。
所以可行性的判断只需要 Tarjan 之后对于每个 SCC 检查一下就好啦。
方案
一个方案
toposort自底向上,我也不太会,请去看论文。
字典序最小方案
建图是一定要建图的,这辈子都不可能不建图的。$O(M)$ 求方案又不会,只有搜索才能骗骗分数这样子。
理论上 $O(NM)$ 的复杂度,实际上跑的不知道快到哪里去了。
遍历每个布尔变量,如果真点或假点已经在点集中了,那么考虑下一个布尔变量,否则把真点加进去试一下,如果不行再加假点,如果还不行,说明无解,退出。否则进行下一个。
需要说明的是,这种做法不需要回溯。也就是说对于一个布尔变量,如果真假都不行,整个问题就无解,而不是回溯到前一个布尔变量调整真假。这是因为我们考虑的布尔变量没有被赋值,这说明前面的布尔变量对应点到这个布尔变量对应点没有边。没有边,调整他们的真假也是没用的。
转化
这个太裸了。出题人不可能让你写裸题吧。所以我们的二元运算不仅可以是析取(OR),还可以是XOR,AND,以及任何能构造推出关系的运算……
实际上,图 $G$ 中的边表示“推出”这一含义。
为了缩短篇幅,我们用 $x,y$ 表示两个布尔变量,列几种典型操作的推出关系。
OR
XOR
AND
AND 非常特殊,它要求两个变量都为真。
我们先介绍如果要求一个变量必须为真时的做法。
$!x\rightarrow x$
显然,这是个矛盾式。如果我们把它加到图中,那么一旦选择了 $x$ 的假点,就会不可避免的顺着边到达 $x $ 的真点,从而推出矛盾。所以所有选择 $x$ 的假点的情况都会变成非法情况从而排除。
那么 AND 的做法也就显而易见了。
NOT XOR
XOR 可以看成相异操作,那么 NOT XOR 就是必须相同。
NOT AND
用摩根律转化为OR。