2-SAT 问题
有关2-SAT问题的详解可见刘汝佳<<训练指南>>P323页,不过这里有个问题: 如何证明”如果当前考虑的变量不管赋值为真还是假都会引起矛盾,可以证明整个2-SAT问题无解(即使调整以前赋值的其他变量也没有用)”.
算法模板:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=10000+10;
struct TwoSAT
{
int n;
vector<int> G[maxn*2];
bool mark[maxn*2];
int S[maxn*2],c;
bool dfs(int x)
{
if(mark[x]) return true;
if(mark[x^1]) return false;
mark[x]=true;
S[c++]=x;
for(int i=0;i<G[x].size();i++)
if(!dfs(G[x][i])) return false;
return true;
}
void init(int n)
{
this->n=n;
for(int i=0;i<2*n;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}
void add_clause(int x,int xval,int y,int yval)
{
x=x*2+xval;
y=y*2+yval;
G[x^1].push_back(y);
G[y^1].push_back(x);
}
bool solve()
{
for(int i=0;i<2*n;i+=2)
if(!mark[i] && !mark[i+1])
{
c=0;
if(!dfs(i))
{
while(c>0) mark[S[--c]]=false;
if(!dfs(i+1)) return false;
}
}
return true;
}
};
分享到:
相关推荐
由对称性解2-SAT问题 个人觉得是一份很好的教材
图论- 2-SAT 问题.rar
基于2-SAT问题的通用算法进行了详细的证明,结合例题图形深入剖析该算法的解题思想,充分挖掘图的性质,更好的解决问题。
由对称性解2-SAT问题_未知作者.ppt
2sat问题的课件,讲解细致易懂!acm/icpc用
2-SAT 经典讲解 ACM必备 2-SAT 经典讲解 ACM必备
非原创,仅供学习交流用。 2-sat不是NPC的!
将SAT问题化为2-SAT子问题进行求解,算法效果比UnitWalk算法高效
可满足问题(SAT)是一个NP-Hard问题。提出了一种求解SAT的新算法(FFSAT)。...使用2-SAT算法-BinSat求解2-SAT子问题,当它不满足时,根据赋值选择新的2-SAT子问题。实验结果表明,采用本算法的结果优于UnitWalk。
有2-SAT图的介绍与解法,有详细的例题讲解。仙人掌图的判断方法与其3个性质,最后还附上模板。
2-sat模板,用来求解图的2-sat问题。共有两种算法,速度都很快,空间复杂度也低。
所为2-sat问题,就是2判断问题。该算法是用拆点的方式建图,用找强连通子图的方法推出矛盾,用以判断2-sat是否可行。经典实现,
信息学竞赛,图论算法,Tarjan,缩点,2-SAT 寒假期间的集训讲课 PPT,主要详细讲解了 Tarjan 算法的思想及应用,同时对于 Tarjan 算法的一个扩展——2-SAT 问题进行了详细的讲解,是图论讲课非常好的课件和资料。
关于2-SAT算法实现的一个小步骤演示。
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
现有一个由N个布尔值组成的序列A,给出一些限制关系,比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等,要确定A[0..N-1]的值,...这个称为SAT问题,特别的,若每种限制关系中最多只对两个元素进行限制,称为2-SAT问题
2-SAT 感觉PPT最关键的部分写的不是很好 。