2-sat总结
算法
构造一个有向图G,每个变量xi拆成两个点2i和2i+1
分别表示xi为假,xi为真
那么对于“xi为真或xj为假”这样的条件
我们就需要连接两条边
2*i —>2*j(表示如果i为假,那么j必须是假)
2*j+1—>2*i+1(表示如果j为真,那么i必须是真)
这就有点像推导的过程
实际上每一个限制条件都会对应两条“对称”的边
接下来逐考虑每个没有赋值的变量,设为x
我们先假定x为假(为什么一定是假,约定俗成了)
之后沿着从ta出发的有向边进行标记
如果在标记过程中,发现有一个点的两种状态都被标记过了
那么我们之前的假设就被推翻了
需要改成x为真,重新标记
如果发现无论这个点赋值成真还是假,都会引起矛盾
可以证明这个2-SAT无解
可能我的叙述有点容易让读者yy
但是一定要注意:
这个算法没有回溯过程
建边:
1.我们利用一条有向边<i,j>,来表示选i的情况下,一定要选j;
2.用i表示某个点是true,那么i'表示某个点是false
3.因为限制的两两之间的关系,所以我们可以通过逻辑关系来建边:
1)如果给出A和B的限制关系,A和B必须一起选,(A and B)||(!A and !B )==true 那么选A必须选B,建边<i,j>和<j,i>还有<i',j'>和<j',i'>
2)如果给出A和B的限制关系,选A不能选B,那么(A && !B)||(!A && B )==true,建边<i,j'>和<j,i'>
3)如果必须选A,那么A==true,建边<i',i>
4)如果A一定不能选,那么!A==true.建边<i,i'>
解决方案
1.求字典序最小的解的方法:
暴力dfs求解(复杂度O(N*M))
2.判断当前的2-sa问题t是否有解
tarjan强连通缩点,加判断(复杂度O(N+M))
3.求出当前的2-sat问题的任意一组解
tarjan强连通缩点+拓扑排序+构建一组解(复杂度O(N+M))
至于想要知道当前元素归到了哪一边,看bl,哪个小就是哪个。(具体见POJ3683)
题目:
1、 POJ 3207
2、 POJ 3683
3、 POJ 3678
4、 POJ 3648
5、 POJ 2723
6、 POJ 2749
最新文章
- MapReduce剖析笔记之五:Map与Reduce任务分配过程
- 注意64位整形,int64,long long
- 关于C#中派生类调用基类构造函数的理解
- 转:[Android问答] 开发环境问题集锦
- Java如何将Exception.printStackTrace()转换为String输出
- lucene 抛出的异常(分享)
- android调用系统自带的的浏览器搜索关键字
- FJ省队集训DAY3 T2
- yarn状态机的可视化
- oschina iOS代码库
- <; 软件工程 第一次作业 >;
- nodejs 初次链接 mongodb 的详细细节
- 2018-2019-2 网络对抗技术 20165237 Exp6 信息搜集与漏洞扫描
- Docker 常用命令(二)
- 一个class标签里面有多个属性时的提取标签
- CentOS7 linux 中提示 bash: ls: 未找到命令...
- feed
- 安装sublime txt3 并且设置为默认的text打开方式
- java面试题:网络通信
- as3.0去除空格