• 欢迎光临~

SCC 和 BCC 题选做(+2-SAT 讲解)

开发技术 开发技术 2022-11-22 次浏览

为了保证文章的整体简洁,代码就不放了。

1. SCC

1. luoguP2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

考虑一个 SCC 内的所有点互相可达,我们完全可以先缩点。
那么能从其他所有点到达的点都在 DAG 上出度为 0 的 SCC 内。(若有多个这样的点那就不存在这样的点了)
做完了。

2. luoguP1262 间谍网络

容易发现如果 SCC 内一个点被支配了,其他的点就也被支配了。
于是直接缩点,图不连通就无解,否则在所有入度为 0 的 SCC 中选出点权最小的点即可。

3. luoguP4819 [中山市选]杀人游戏

危险题面。

4. luoguP3119 [USACO15JAN]Grass Cownoisseur G

5. AT3945 [ARC092D] Two Faced Edges

6. luoguP7737 [NOI2021] 庆典

2. BCC

1. luoguP2860 [USACO06JAN]Redundant Paths G

注意一个边双中的点已经满足要求。否则路径上的边都是割边,矛盾。
于是对边双缩点转到树上。显然树上的两点间都已经有了一条路径。
我们发现新增边 ((u,v)) 会使树上 (u,v) 之间的链上的点都满足要求。
那么容易发现最优的策略是每次选两个儿子进行连边。
答案就为 (leftlceildfrac{l}{2}rightrceil),其中 (l) 是树的叶子数。

2. CF555E Case of Computer Network

显然我们可以对边双进行定向,使边双里的点互相可达。于是做边双缩点。
然后因为图可能不是连通的,我们需要判断询问的两个点在不在一个连通块里。
在一个连通块里的,想要满足条件就必须将树上从 (s_i)(t_i) 的链都给定到一个方向。
于是我们考虑树上差分维护树边定的方向,判断互相有没有矛盾即可。

3. SP2878 KNIGHTS - Knights of the Round Table

4. luoguP3225 [HNOI2012]矿场搭建

3. 2-SAT

首先 SAT 问题是啥?
个人理解: SAT 问题是一类特殊的 bool 方程.
首先, 方程要有变量. 所以我们有一些 bool 变量 (p_1,p_2,cdots,p_n).
其次, 方程要有条件. 我们有若干个条件需要同时被满足, 每个条件都是如下的形式:
((p_{a_1}) 为真/假) 或 ((p_{a_2}) 为真/假) 或 (cdots) 或 ((p_{a_k}) 为真/假)
也就是说 对于每个条件, 至少要有一个 (p_{a_i}) 为真/假 要被满足.
如果每个条件的限制个数最多为 (k), 那我们称其为 k-SAT 问题.

不幸的是, 已经证明了 (kgeqslant3) 时 k-SAT 问题是 NPC 问题.
因此我们这里只讨论 2-SAT 问题的解法.

首先我们把 2-SAT 问题再具体化一些.
给定 bool 变量 (p_1,p_2,cdots,p_n) 和一堆条件, 每个条件是以下五种之一:

  1. (p_i) 为真
  2. (lnot p_i) 为真, 即 (p_i) 为假
  3. (p_ilor p_j) 为真, 即两变量的或为真
  4. (lnot p_i lor p_j) 为真
  5. (lnot p_ilorlnot p_j) 为真

2-SAT 的特殊之处在于, 我们可以把这些条件写成蕴含式. (包含逆否命题)

  1. (lnot p_iRarr p_i)
  2. (p_iRarrlnot p_i)
  3. (lnot p_iRarr p_j, lnot p_jRarr p_i)
  4. (p_jRarr p_i, lnot p_iRarr lnot p_j)
  5. (p_iRarrlnot p_j, p_jRarrlnot p_i)

然后一下子就有了图论的感觉! 考虑建立 (2n) 个点表示 (p_1,cdots,p_n)(lnot p_1,cdots,lnot p_n), 然后按照上面的蕴含式连边.
我们知道蕴含有传递性, 对应到图上其实就是连通性.
如果出现了强连通分量, 那就意味着强连通分量内的命题等价.
很明显, 若 (p_i)(lnot p_i) 在同一个强连通分量里, 那么原方程就无解了.
看上去是一定有解的. 我们考虑直接把解构造出来.
我们发现如果有 (lnot p_irightsquigarrow p_i), 那此时就对应了 (p_i) 真, 我们选择 (p_i). 换句话说, 我们选择拓扑序大的一个.
这样选择是否一定是正确的?
假设存在 (lnot p_irightsquigarrow p_i,lnot p_jrightsquigarrow p_j), 但是 (p_irightsquigarrow lnot p_j).
显然有逆否命题, (p_jrightsquigarrowlnot p_i). 但是根据上面拓扑序的大小规律, 轻松就能推出矛盾. 因此 (p_irightsquigarrow lnot p_j) 不可能存在, 我们构造出的是一组合法解.

P4782 【模板】2-SAT 问题
实际操作的时候因为 tarjan 染色就已经求出来拓扑序了, 所以不用再跑一遍.

1. luoguP4171 [JSOI2010] 满汉全席

纯纯的板子. 略.

2. luoguP3825 [NOI2017] 游戏

没有 x: 2-SAT 板子.
有 x: 好家伙是 3-SAT?
注意到 x 的数量并不多, 考虑暴力枚举.
但是枚举是 AB, AC 还是 BC 时间复杂度就直接变成 (O(3^d(n+m))), 寄.
等等我们真的需要枚举三种情况吗?
实际上两种就够了, 比如枚举 AB 和 AC. 因为这已经包含了这个位置选择 A, B, C 是否可行.
时间复杂度 (O(2^d(n+m))).

程序员灯塔
转载请注明原文链接:SCC 和 BCC 题选做(+2-SAT 讲解)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com