浅谈2-SAT

什么是2-SAT

2-sat问题是一个逻辑互斥问题，与我们小时候做过的一道数学题一样。

A,B,C三个人中有两个女生，其中如果A为女生，B一定不是女生，而且A与C性别相同，求A，B，C的性别。

这是一道非常简单的题目，我们可以简单分析一下。

我们用\(f[i]=0\)表示\(i\)为女生，\(f[i]=1\)表示\(i\)为男生，那么“如果A为女生，B一定不是女生”这句话可以表示为\(if (f[1]==0) f[2]=1;\)反过来也一样，即若B为女生，A一定不是。同理，“A与C性别相同”这句话就可以表示为\(f[3]=f[1]\)。而这，就是一道最简单的2-sat问题。

那么在此基础上，我们就可以开始分析2-sat了。

概念

SAT是适定性(Satisfiability)问题的简称 。一般形式为k-适定性问题，简称 K-SAT。

可以证明，当\(K>2\)时，K-SAT是NP完全的。因此一般讨论的是k=2的情况，即2-SAT问题。

我们通俗的说，就是给你n个变量\(a_i\)，每个变量能且只能取0/1的值。同时给出若干条件，形式诸如\((not)a_i\) opt \((not)a_j = 0/1\)，其中opt表示\(and,or,xor\)中的一种

而求解2-SAT的解就是求出满足所有限制的一组a

如何求解2-sat

我们发现，每一个条件如上题中“如果A为女生，B一定不是女生”我们可以考虑将A与B拆点，拆为A为女（\(a_0\)）、A为男（\(a_1\)）、B为女（\(a_2\)）和B为男（\(a_3\)）。那么这个条件我们就可以将\(a_1\)向\(a_4\)连一条单向边，\(a_3\)向\(a_2\)连一条单向边。那么当我们发现它成为了环时，准确来说是当\(a_i\)和\(a_{i+1}\)在同一个环中，也就是说某人（hzr）既要当男生又要当女生时，显然是不成立的，此时是无解的。若没有出现这种情况，就说明存在这样一组解。

我们可以举一些简单的例子来总结下连边的规律（用i′表示i的反面）：

\(i,j\)不能同时选：选了\(i\)就要选\(j′\)，选\(j\)就要选\(i′\)。故\(i \rightarrow j′\),\(j \rightarrow i′\)。一般操作即为\(a_i\) ^ \(a_j=1\)

\(i,j\)必须同时选：选了\(i\)就要选\(j\)，选\(j\)就要选\(i\)。故\(i \rightarrow j\),\(j \rightarrow i\)。一般操作即为\(a_i\) ^ \(a_j\)=0

\(i,j\)任选（但至少选一个）选一个：选了\(i\)就要选\(j′\)，选j就要选\(i′\)，选\(i′\)就要选\(j\)，选\(j′\)就要选\(i\)。故\(i \rightarrow j′\),\(j \rightarrow i′\),\(i′ \rightarrow j\),\(j′ \rightarrow i\)。一般操作即为\(a_i\) ^ \(a_j\)=1

\(i\)必须选：直接\(i′\)→\(i\)，可以保证无论怎样都选\(i\)。一般操作为给出的\(a_i=1\)或\(a_i\) & \(a_j=1\)

解法1——DFS

• 对于每个当前不确定的变量\(a_i\)，令\(a_i=0\)然后沿着边DFS访问相连的点。
• 检查如果会导致任意一个\(j\)与\(j′\)都被选，那么撤销。否则令a_i=0
• 否则令\(a_i=1\)，重复2。如果还不行就无解。
• 继续考虑下一个不确定的变量

这里贴一下DFS的板子

#include
using namespace std;
const int maxn=4e6+5;
struct edge{
	int nex,to;
}e[maxn];
int fl[maxn],n,m,beg[maxn],tot,s[maxn],cnt;
int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void add(int x,int y) {
	e[++tot]=(edge){beg[x],y};
	beg[x]=tot;
}
bool dfs(int now) {
	if (fl[now^1]) return true;
	if (fl[now]) return false;
	s[++cnt]=now;fl[now]=1;
	for (int i=beg[now];i;i=e[i].nex) {
		int nex=e[i].to;
		if (dfs(nex)) return true;
	}
	return false;
}
int main() {
	n=read();m=read();
	for (int i=1;i<=m;i++) {
		int x=read()-1,u=read(),y=read()-1,v=read();
		add(x*2+1-u,y*2+v);
		add(y*2+1-v,x*2+u);
	}
	for (int i=0;i