描述

一些布尔变量组成若干二元简单析取式,求使得这些简单析取式全部为真的赋值方案。

分析

要不我们先建个图?

一个布尔变量有真假两种情况。所以我们令点 $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$。

也就是:

$$u’_i\in S\rightarrow u_j \in V$$

……那我们顺手连个边好了。

记一个简单析取式为两个有序二元对,就这样连边:

$\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

$$!x\rightarrow y$$

$$!y\rightarrow x$$

XOR

$$x\Leftrightarrow !y$$

$$y\Leftrightarrow !x$$

AND

AND 非常特殊,它要求两个变量都为真。

我们先介绍如果要求一个变量必须为真时的做法。

$!x\rightarrow x$

显然,这是个矛盾式。如果我们把它加到图中,那么一旦选择了 $x$ 的假点,就会不可避免的顺着边到达 $x $ 的真点,从而推出矛盾。所以所有选择 $x$ 的假点的情况都会变成非法情况从而排除。

那么 AND 的做法也就显而易见了。

NOT XOR

XOR 可以看成相异操作,那么 NOT XOR 就是必须相同。

$$x\Leftrightarrow y$$

$$-x\Leftrightarrow -y$$

NOT AND

用摩根律转化为OR。