【学习笔记】 2-SAT问题

(2-SAT)问题就是给定一串布尔变量，每个变量只能为真或假。

要求对这些变量进行赋值，满足布尔方程。

会有一些形如 (x_1||x_2) 或者 (x_5||(!x_6)) 的条件

所谓布尔方程就是赋值之后满足所有的条件

如果这个条件变成三或者三以上个(x)相关的了，就只能(2^n)枚举了，即 (N-SAT) 问题是 (NP) 完全

---

怎么做呢？

首先拆点: (i->i) 同时 ((!i)->i+n)

然后我们我们考虑建图的时候

对于每一个条件： (a||b) ，连上 ((!a)->b) 和 ((!b)->a) 的两条有向边

这里可以理解成【(b) 假则 (a) 必须真，(a) 假则 (b)必须真】

考虑 (tarjan) 求一波强连通分量，如果有 (scc[i]==scc[i+n]) 直接无解

显然真假是不一样的（就是不能赋相同的值）

如果要跑方案，就直接输出([scc[i]<scc[i+n]]) 就好

例题

1.【模板】(2-SAT)问题

2.JSOI2010 满汉全席

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=4e6+10;
	int n,m,a,b,x,y,tim,top,tot,cnt;
	int dfn[N],low[N],st[N],vis[N],scc[N],head[N];
	struct node{int to,nxt;}e[N];
	inline void add(int u,int v){e[++cnt].nxt=head[u],e[cnt].to=v; head[u]=cnt; return ;}
	inline void tarjan(int u,int fa)
	{
		dfn[u]=low[u]=++tim; st[++top]=u; vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int t=e[i].to; if(t==fa) continue;
			if(!dfn[t]) tarjan(t,u),low[u]=min(low[u],low[t]);
			else if(vis[t]) low[u]=min(low[u],dfn[t]);
		}
		if(dfn[u]==low[u])
		{
			tot++; while(st[top]!=u) scc[st[top]]=tot,vis[st[top--]]=0;
			scc[st[top]]=tot; vis[st[top--]]=0;
		}
		return ;
	}
	signed main()
	{
		n=read(); m=read();
		for(int i=1;i<=m;++i)
		{
			a=read(); x=read(); b=read(); y=read();
			if(!x&&!y) add(a+n,b),add(b+n,a);
			if(!x&&y) add(a+n,b+n),add(b,a);
			if(x&&!y) add(a,b),add(b+n,a+n);
			if(x&&y) add(a,b+n),add(b,a+n);
		}
		for(int i=1;i<=2*n;++i) if(!dfn[i]) tarjan(i,0);
		for(int i=1;i<=n;++i)
		{
			if(scc[i]==scc[i+n]) return puts("IMPOSSIBLE"),0;
		}
		puts("POSSIBLE"); for(int i=1;i<=n;++i) printf(scc[i]>scc[i+n]?"1 ":"0 ");
		return 0;
	 } 
}
signed main(){return yspm::main();}