2-SAT

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

看看模板题

Description

有 \(n\) 个布尔变量 \(x_1∼x_n\) ，另有 \(m\) 个需要满足的条件，每个条件的形式都是 \(「xi 为 true / false 或 xj 为 true / false」\)。比如 「\(x1\) 为真或 \(x3\) 为假」、「 \(x7\) 为假或 \(x2\) 为假」。
2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

Solution

我们发现，题目的要求是在两个条件中任选一个满足。也就是说，如果我们不选A条件，就必须要选B条件；同理，我们不选B条件，就必须要选A条件。
现在，我们假设边(A,B)表示选了A条件，就必须要选B条件。那么根据上面的推论，我们发现现在我们应该连边(非A条件，B条件)，(非B条件，A条件)。
这个时候我们能发现，如果A条件和非A条件在同一个强连通分量里面，证明选了A条件之后我们就要选非A条件，这自相矛盾。这个时候无解。

#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
int n,m,x,y,a,b;
struct node{
	int to,nxt;
}e[N<<2];
int head[N],cnt;
int dfn[N],low[N],stk[N],tim,scc,vis[N],top,id[N];
void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	stk[++top]=u;
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		int v;
		++scc;
		do{
			v=stk[top--];
			vis[v]=0;
			id[v]=scc;
		}while(v!=u);
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d %d",&x,&a,&y,&b);
		add(x+!a*n,y+b*n);
		add(y+!b*n,x+a*n);
	}
	for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
	{
		if(id[i]==id[i+n])
		{
			printf("IMPOSSIBLE\n");
			return 0;
		}
	}
	printf("POSSIBLE\n");
	for(int i=1;i<=n;i++)
	{
		if(id[i]<id[i+n]) printf("0 ");
		else printf("1 ");
	}
	return 0;
}

看看应用CF1697F

Description

构造一个长度为 \(n\) 的数列 \(a\) ,其中 \(1\leq a_i \leq k\) 且 \(a\) 不降，即对所有 \(1\leq i \leq n-1\) , \(a_i \leq a_{i+1}\) 。给出 \(m\) 个约束，有三种约束，其中：
\(1\) \(i\) \(x\) ,表示 \(a_i\neq x\)
\(2\) \(i\) \(j\) \(x\) ,表示 \(a_i+a_j\leq x\)
\(3\) \(i\) \(j\) \(x\) ,表示 \(a_i+a_j\geq x\)
现在有 \(t\) 组数据，要求你给出这个数列，无解输出 \(-1\) 。

Solution

断断续续调了3天的题，细节好多。
首先发现题目让我们通过好多限制寻找到一个可行解，考虑 2-SAT。2-SAT 的特点是每个变量只有两种取值，显然我们现在的 \(n\) 个数，每个数都有 \(k\) 种取值，怎么办呢，我们发现 \(2\leq k \leq 10\) , \(k\) 的值域非常小，那么我们把每个数都拆成 \(k\) 个点。这样我们一共只有 \(n*k\) 个点。其中 \(A_{i,j}\) 表示 \(a_i\geq j\)。
PS:这里之所以不定义成 \(A_{i,j}\) 表示 \(a_i=j\) 是因为

然后在回头看那 \(3\) 个限制

1. \(a_i\neq x\) 等价于「若 \(a_i\geq x\) 则 \(a_i\geq x+1\)」
2. \(a_i+a_j\leq x\) 等价于
   「\(\forall y\) 若 \(a_i\geq y\) 则 \(\neg(a_j\geq x-y+1)\) , \(\forall y\) 若 \(a_j\geq y\) 则 \(\neg(a_i\geq x-y+1)\)」
3. \(a_i+a_j\geq x\) 等价于
   「\(\forall y\) 若 \(\neg(a_i\geq y)\) 则 \(a_j\geq x-y+1\) , \(\forall y\) 若 \(\neg(a_j\geq y)\) 则 \(a_i\geq x-y+1\)」

然而真的只有这 \(3\) 个限制吗，不是！

1. 题目中说道 \(a\) 序列不降,即 \(a_i\leq a_{i+1}\) 等价于「\(\forall x\) 若 \(a_i\geq x\) 则 \(a_{i+1}\geq x\)」
2. 还有最基本的「若 \(a_i\geq x\) 则 \(a_i\geq x-1\)」
3. 还有更基本的 \(a_i\) 必须大于等于1，等价于「若 \(\neg(a_i\geq1)\) 则 \(a_i\geq1\)」

这就完啦？你别说你还真别说，还没有……
我们考虑一下前三条有没有什么问题，发现有大问题。

1. 对于限制一，如果 \(x=k\) 显然 \(a_i\geq x\) 不可取但还没有 \(a_i\geq x+1\) 这个变量，所以等价于「若 \(a_i\geq x\) 则 \(\neg(a_i\geq x)\)」
2. 对于限制二，如果 \(x<=k\) 可能会有 \(a_i=x\) \(a_j=0\) 或者 \(a_j=x\) \(a_i=0\) 的情况，这也不行，那么等价于「若 \(a_i\geq x\) 则 \(\neg(a_i\geq x)\) , 若 \(a_j\geq x\) 则 \(\neg(a_j\geq x)\)」
3. 对于限制三，如果 \(x>k\) 要避免两个数有大于 \(k\) 的情况，也就是要避免有数小于 \(x-k\) 等价于「若 \(\neg(a_i\geq x-k)\) 则 \(a_i\geq x-k\) , 若 \(\neg(a_j\geq x-k)\) 则 \(a_j\geq x-k\)」

终于把限制写完了，另外由于 2-SAT 的对称性，上述所有条件的反向边也要连，注意这里的反向边不仅逻辑要反先后顺序也要反，这就不得不提到2-SAT中连边顺序的重要性,即满足……才……这样连一条有向边，反过来意思不同就错了。

太对了最后看看怎么输出答案，判断是否又解是好做的和模板题一样，关键是又解咋办捏，我们对于每个位置，从大到小枚举取值，如果可以就输出，这样选到的值一定是最大的，就避免了因为某个位置选的值小而使序列不满足序列不降这一条件。然后你终于做完了！

Code
另外很清晰的题解

Tricks

1. 2-SAT的对称性，顺序不能反。

2. 有多种取值且值域很小的时候考虑拆点。

3. 限制不仅仅只有题中给的，找找隐藏限制2-SAT