欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

(模板)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;
}