Algorithm Description

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

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

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

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

首先扯一句，如果这个条件变成三或者三以上个\(x\)相关的了，就只能\(2^n\)枚举了

（好像是 \(N-SAT\) 问题是 \(NP\) 完全的）

然后我们思考如何求解这样的问题

前人告诉我们，可以把这些变量转移到图上进行操作

\[Begin
\]

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

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

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

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

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

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

\[Finished
\]

如果要跑方案，就直接输出\([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();}

瞎看吧，这个 \(add\) 压行有点严重了，没去格式化 \(2333\)

巴特西

【学习笔记】 2-SAT问题

Algorithm Description

例题

Code:

最新文章

热门文章