(模板)2-SAT
程序员文章站
2022-04-09 18:54:27
(模板)2-SAT 题目描述 有n个变量,m条语句,没个形如:xi为a或xj为b(a,b=0或1)... 判断是否有解,有的话构造出来一组解 思路: 将每个变量分为两个点,取0和取1(i和i+n) 对于每条语句可以转换为若xi取(1-a)则xj必须取b,若xj取(1-b)则xi必须取a,按照这样的关 ......
(模板)2-sat
题目描述
有n个变量,m条语句,没个形如:xi为a或xj为b(a,b=0或1)...
判断是否有解,有的话构造出来一组解
思路:
- 将每个变量分为两个点,取0和取1(i和i+n)
- 对于每条语句可以转换为若xi取(1-a)则xj必须取b,若xj取(1-b)则xi必须取a,按照这样的关系连边
- 跑一遍tarjan,则在同一个强连通分量中如果取了一个点,那么一定要取其中的其他的点,如果i与i+n在同一个强连通分量,则一定无解
- 有解时,先缩点,然后每次找到出度为0的点,选取它,并删除即可,这样得到的操作序列就相当于倒着跑一遍拓扑排序(因为拓扑排序是先找入度为0的点)
- 又注意到tarjan后的col数组其实就是一个自底向上的拓扑序,所以我们每次选出度最小的点就相当于选col小的点
代码:
#include <cstdio>
#include <stack>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
#define res register int
inline int read()
{
int x=0,f=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int n=4e6+5,m=4e6+5;
int head[n],fron[m],ver[m],nxt[m];
int tot,n,m;
inline void add(int x,int y)
{
ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot;
}
int dfn[n],low[n],col[n],colnum,num;
bool ins[n];
stack <int> s;
void tarjian(int x)
{
dfn[x]=low[x]=++num;
s.push(x); ins[x]=1;
for(res i=head[x],y ; i ; i=nxt[i])
if(!dfn[y=ver[i]])
tarjian(y),low[x]=min(low[x],low[y]);
else
if(ins[y])
low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])
{
++colnum; int y;
do {
y=s.top(); s.pop();
ins[y]=0; col[y]=colnum;
}while(x!=y);
}
}
// xi=xj-> yi=yj
int opp[n];
inline void work()
{
for(res i=1 ; i<=n*2 ; ++i)
if(!dfn[i]) tarjian(i);
for(res i=1 ; i<=n ; ++i)
{
if(col[i]==col[n+i])
{
puts("impossible");
return;
}
}
puts("possible");
for(res i=1 ; i<=n ; ++i)
printf("%d ", col[i] > col[i+n]);//col[i]<col[i+n]时选i->取0
}
int main()
{
n=read(); m=read();
for(res i=1 ; i<=m ; ++i)
{
int a=read(),b=read(),c=read(),d=read();
// a=b^1 -> c=d
// c=d^1 -> a=b
add(a+(b^1)*n,c+d*n); add(c+(d^1)*n,a+b*n);
}
work();
return 0;
}