2-SAT速成

本文只做总结性说明

2-SAT

2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题

2-SAT问题定义比较简单

有n个布尔变量x_1-x_n。给出m个限制关系,每个关系最多只对两个变量进行限制。求一组取值使得满足所有限制。

这里的限制例如:选A必选B 或是 A,B至少选一个

解决方法

2-SAT问题所构成的图具有对称性

对于两个点来说

即若选A必选B,那么选B必选A

根据这种性质,前人总结出了一种方法

将一个点A拆为A,A'

1.若选A必选B,那么从A向B连一条边

2.tarjan缩点(把时间从O(NM)优化至O(n) )

3.判断是否A'A是否在同一强联通分量中

对于需要输出方案的题目

4.根据缩完点的图,建出其反图

5.对反图进行拓扑排序

6.根据拓扑排序的顺序标记答案

经典模型

  • 两者(A,B)不能同时取

那么选择了A就只能选择B’,选择了B就只能选择A’

连边A→B’,B→A’

  • 两者(A,B)不能同时不取

那么选择了A’就只能选择B,选择了B’就只能选择A

连边A’→B,B’→A

  • 两者(A,B)要么都取,要么都不取

那么选择了A,就只能选择B,选择了B就只能选择A,选择了A’就只能选择B’,选择了B’就只能选择A’

连边A→B,B→A,A’→B’,B’→A’

  • 两者(A,A’)必取A

  连边A’→A

A'A不能同时出现,选A'必选A,故只能单独选A

例题

由简单到简单2333

POJ 3207

BZOJ 1823

洛谷 P3209

BZOJ 2199

POJ 3683

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏锦小年的博客

复杂网络(1)--图论的基本理论

1 图论的基本概念 1.1 图(graph)及其分类 (1) 图的定义:图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组,记为G=(...

26210
来自专栏小樱的经验随笔

hihoCoder #1142 : 三分求极值

#1142 : 三分·三分求极值 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 这一次我们就简单一点了,题目在此: ? 在直...

3499
来自专栏ml

nyoj-----幸运三角形

幸运三角形 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述         话说有这么一个图形,只有两种符号组成(‘+’或者‘-’...

30110
来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

1.3K8
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

1231
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

2848
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1213
来自专栏机器学习原理

示例三(3)——人物画像特征提取

4283
来自专栏小鹏的专栏

tensorflow使用BN—Batch Normalization

注意:不要随便加BN,有些问题加了后会导致loss变大。 上一篇是 Batch Normalization的原理介绍,看一下tf的实现,加到卷积后面和全连接层...

9177
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2493

扫码关注云+社区

领取腾讯云代金券