文章目录

• 前言
• 实现
• 代码

所谓2-SAT，就是解决两个SAT的问题

（逃）

前言

SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 k>2 时该问题为 NP 完全的。所以我们只研究 k=2 的情况。
2-SAT，简单的说就是给出 k 个集合，每个集合有两个元素，已知若干个 (a,b)，表示 a 与 b 矛盾（其中 a 与 b 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 n 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。

感觉2-SAT也就是听起来高大上
理解和代码实现其实都不难
题目很多也都很板
不明白为什么这是个模板就紫的算法
这不比网络流、平衡树之类的阳间多了

实现

考虑建图tarjan缩点
然后判断，若a与a’同属于一个分量，则矛盾
否则构造方案选tarjan染色编号小的那个点
这利用了tarjan栈的性质，相当于反的拓扑序
一个讲的很清楚的地方

代码

洛谷模板传送门

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=4e6+100; const int mod=998244353; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m; int id[N][2]; struct node{int to,nxt; }p[N]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt; } int dfn[N],low[N],tim,zhan[N],col[N],tot,top; void tarjan(int x){dfn[x]=low[x]=++tim;zhan[++top]=x;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(!dfn[to]){tarjan(to);low[x]=min(low[x],low[to]);}else if(!col[to]) low[x]=min(low[x],dfn[to]);}if(dfn[x]==low[x]){col[x]=++tot;while(zhan[top]!=x){col[zhan[top--]]=tot;}top--;} } int main(){memset(fi,-1,sizeof(fi));n=read();m=read();for(int i=1;i<=n;i++){id[i][0]=i;id[i][1]=i+n;}tot=2*n;for(int o=1;o<=m;o++){int i=read(),a=read(),j=read(),b=read();addline(id[i][!a],id[j][b]);addline(id[j][!b],id[i][a]);}for(int i=1;i<=2*n;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=n;i++){if(col[i]==col[i+n]){printf("IMPOSSIBLE\n");return 0;}}printf("POSSIBLE\n");for(int i=1;i<=n;i++){printf("%d ",col[i]>col[i+n]);} } /* 4 1 2 3 4 */

总结

以上是生活随笔为你收集整理的模板：2-SAT问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。