记录一些做过的 2-sat 题目
P4171 [JSOI2010]满汉全席
很裸的 2-sat
题意：(n) 种食材，每种可以按照满式或汉式来烹饪，有 (m) 个要求，每个要求所有做出的菜品中，必须有指定的两个 满式/汉式 烹饪的第 (x) 种食材 中，至少一个
多测
就把每个食材，拆乘用满式和用汉式两个点，然后题目中给出的是“或”的关系，用经典 2-sat 模板的方法建图跑 tarjan 就行
其实 满式和汉式 对应的就是经典模型中的 真和假
P5782 [POI2001]和平委员会
每个党在议会中有 (2) 个代表。代表从 (1) 编号到 (2n)。 编号为 (2i-1) 和 (2i) 的代表属于第 (i) 个党派。
选一些人当代表，满足：
- 每个党派都在委员会中恰有 (1) 个代表。
- 如果 (2) 个代表彼此厌恶，则他们不能都属于委员会。
给出互相厌恶的信息，求是否有满足要求的选法，如果有，升序输出任意一种
也是显然的 2-sat
对于给出的互相厌恶的两个人，先判一下在他们在自己的党派中分别是第几个人
对于每个党，拆成两个点，然后每个点代表是选第一个人还是选第二个
连边的依据就是，如果选了这个人，一定要再选哪个人
我的写法中是，每个党中第一个人用 (1) 到 (n)，编号，第二个人用 (n+1) 到 (2n) 编号
给出的信息的连边方式是，对于互相厌恶的每一方，都向对方的党派中，的另一个人连边，表示如果选择这个人，在对方党派中，就必须选另一个人（因为不能同时选这个人和对方）
然后跑 tarjan 就行了
代码
P6378 [PA2010]Riddle
(n) 个点 (m) 条边的无向图被分成 (k) 个部分。每个部分包含一些点。
请选择一些关键点，使得每个部分 至多 有一个关键点，且每条边 至少 有一个端点是关键点。
比上面两个稍微难点
还是把每个点拆成两个，分别表示这个点选为关键的还是不选
(1,cdots ,n) 的编号表示选，(n+1,cdots ,2n) 的编号表示不选
首先考虑第二条限制，每条边 至少 有一个端点是关键点
连 ((u+n,v),(v+n,u)) 两条边，表示一段如果不选，一定能导出另一端要选
再考虑第一种，首先有种朴素的想法，就是每一个点，设为 (x)，设和它在同一个部分内的点编号分别是 (a_i)，用 (x) 分别向 (a_i+n) 连边
就是如果 (x) 被选了，一定能导出 (a_i) 都不能选
但边数达到了 (n^2)，不可行
可以用一种 前缀和优化，以前并没有听说过这种方法，还是看来题解才知道的
要新建一堆点，(pre_i) 表示在当前的这个部分，前 (i) 个点中，有一个点已经被选了，而 (pre_i') 表示前 (i) 个点，一个都没被选
然后也是用 2-sat 的连边规则，假设某个点表示的信息成立，那么就用它，连向由它表示的这个信息，一定能导出的信息，所对应的点
具体的连边方式比较复杂，可以想到，如果当前在考虑一个部分的第 (i) 个点，与它有关的有 (a_i,a_i',pre_i,pre_i',pre_{i-1},pre_{i-1}')，这里是用 (a_i,a_i') 分别表示代表信息第 (i) 个点 选/不选 的点
然后如果很懵的话可以 (6 imes 5=30) 次两两分别枚举，看一下有没有关系，看起来麻烦，其实有好多一想就知道没关系的可以直接跳过了
下面的括号表示连边，是有向的
- ((a_i,a_i'),(pre_i,pre_i'),(pre_{i-1},pre_{i-1}'))，这些并不在 2-sat 连边考虑范围内，然后把他们反过来也是一样
- ((a_i,pre_i),(a_i,pre_{i-1}'))，选了第 (i) 个，前 (i) 个中有被选的，前 (i-1) 个没有
- (a_i',pre_i,pre{i-1}')，这三个信息并不能推出什么，所以没有它们的出边
- ((pre_i',a_i'),(pre_i',pre_{i-1}'))，显然
- ((pre_{i-1},pre_i),(pre_{i-1},a_i'))，前 (i-1) 个中有被选的，前 (i) 个肯定也有，且第 (i) 个不能选
就可以了，题目也并没有要求给出方案
代码中，用 (1) 到 (n) 表示 (a_i)，(n+1) 到 (2n) 表示 (a_i')，(2n+1) 到 (3n) 是 (pre_i)，(3n+1) 到 (4n) 是 (pre_i')
代码
P3825 [NOI2017]游戏
(nle 5cdot 10^4,mle 10^5,dle 8)
如果没有 ( exttt{x}) 地图，那么对于每一场比赛，都只能使用两种车子
那么对每个比赛，可以用两个点，分别表示对于当场比赛，用的是能用的车子中的第几个（比如一场比赛不能用 ( exttt{A})，那么 ( exttt{B}) 就是第一个，( exttt{C}) 就是第二个
直接按 2-sat 建图跑 tarjan
考虑如何建图，下面描述中，字母意义就对应了题目中游戏要求描述的四元组中的字母，设第 (i) 个比赛不能用车 (s_i)
- (s_i=h_i)，不能用 (h_i)，说明这种情况永远不会发生，直接忽略就行
- (s_j=h_j)，(j) 比赛不能用 (h_j)，说明我们不能让这种情况发生，否则就违反了规则，那么由 (h_i)，向连边比赛 (i) 能用的另一个车连边，表示如果用车 (h_i) 成立（这是不符合我们要求的），就要强制它选另一辆，也就是让另一个车成立
- 其它情况。由 (h_i) 向 (h_j) 连边就行，意义就是题目中要求的，(i) 用 (h_i) 则 (j) 必须用 (h_j)
如果 tarjan 判断成立，按照 tarjan 缩点时强连通分量与拓扑序相反的性质，就能构造出一组解
那么有地图 ( exttt{x}) 怎么办？
由于 ( exttt{x}) 很少，所以可以 (2^d) 枚举每一个 ( exttt{x}) 是 ( exttt{a}) 或 ( exttt{b})，这样分别能使用 ( exttt{A,B}) 车和 ( exttt{B,C}) 车，包含所有情况，就不用考虑 ( exttt{x}) 是地图 ( exttt{c}) 的情况了
所以复杂度 (O(2^dm))，洛谷bzoj都能过，但uoj加了一组恶心的extra，被卡成了97，把递归改成循环再加上火车头还是不行/kk
代码
P3513 [POI2011]KON-Conspiracy
Byteotia 的领土被占领了，国王 Byteasar 正在打算组织秘密抵抗运动。国王需要选一些人来进行这场运动，而这些人被分为两部分：
一部分成为同谋者活动在被占领区域，另一部分是后勤组织在未被占领的领土上运转。但是这里出现了一个问题：
- 后勤组织里的任意两人都必须是熟人，以促进合作和提高工作效率。
- 同谋者的团体中任意两人都不能是熟人。
- 每一部分都至少要有一个人。
国王想知道有多少种分配方案满足以上条件，当然也有可能不存在合理方案。
比较有思维难度，思路来自这个blog：https://www.cnblogs.com/chenyushuo/p/5128665.html
首先，可以用一个很显然的 2-sat 求出一种安排方式，具体方法是 (i) 认识 (j)，就连边 (i+n,j)，否则连 (i,j+n)
其中 (1cdots n) 是后勤，(n+1cdots 2n) 是同谋
然后从这种方式看看能转变成几种其它方式，显然不能同时让两个人从一个集合到另一个集合（比如两个互相认识的后勤同时到了同谋，那么它们互相认识就出现了问题）
所以转换方式是，一个人自己转变集合，或者两个集合交换一个人
首先定义 (x) 的“冲突点”，如果 (x) 是后勤，那么冲突点是在同谋中的 (x) 认识的人，如果 (x) 在同谋，冲突点是在后勤中 (x) 不认识的人
记 (x) 的冲突点个数为 (num_x)
- (num_x>1)，则无法让 (x) 到另一个集合
- (num_x=1)，需要交换 (x) 和他的唯一一个冲突点，但是如果它的冲突点的 (num) 不为 (0)，也不能交换（两个点显然不能互为冲突点，那么如果它的冲突点也有冲突点，就肯定和它的集合内的某个点冲突，除非和这个冲突的点互换，它的冲突点是不能来的它的集合的）
- (num_x=0)，可以直接把 (x) 放到对面（如果 (x) 所在集合大小大于 (1)），也可以和对面某个冲突点个数为 (0) 的点呼唤
最后这个两个集合中，冲突点为 (0) 的点互换产生的答案，可以拿两遍冲突点个数为 (0) 的点的个数一相乘得到
可以想到，这样统计答案包含了所有情况
POJ2749 Building roads
给出一些点和它们的坐标，以及两个链接点，所有点都要链接到恰好一个链接点上
给出 (A) 对点，这些点任意一对不能链接同一个链接点。还有 (B) 对点，任意一对必须连接到一个链接点
问有没有可行方案，如果有，两个点之间最大距离的最小值是多少，距离按曼哈顿距离计算
每个点拆成 连到第一个点 和 连到第二个点，然后二分一个最大距离，就可以得到关于距离的限制条件，连边即可
坑
LOJ#6036.「雅礼集训 2017 Day4」编码
P5332 [JSOI2019]精准预测
这俩题细节好像挺多，做了一上午没做出来自闭了/kk
LOJ#571.「LibreOJ Round #11」Misaka Network 与 Accelerator，一开始以为是个线段树优化连边的题，后来写着写着发现不对，看网上说要用边分治，之后应该就要学这一块了，到时候应该会补
然而难度稍大的我似乎都没做qaq