LG4782 「模板」2-SAT问题 2-SAT

问题描述

题解

对于一个限制条件，建边如下：

如果\(x,-x\)在同一个强联通分量里，则不行，否则可以

构造方案：输出\(bel_i<bel_{i+n}\)

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') fh=-1,ch=getchar();

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

const int maxn=2000007;

const int maxm=2000007;

int Head[maxn],to[maxm],Next[maxm],tot;

int n,m;

void add(int x,int y){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;

}

bool ins[maxn];

int dfn[maxn],low[maxn],ind;

int sta[maxn],top;

int bel[maxn],cnt;

void tarjan(int x){

	dfn[x]=low[x]=++ind,sta[++top]=x,ins[x]=1;

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(dfn[y]){

			if(ins[y]) low[x]=min(low[x],dfn[y]);

		}

		else{

			tarjan(y);

			low[x]=min(low[x],low[y]);

		}

	}

	if(dfn[x]==low[x]){

		++cnt;

		while(sta[top]!=x){

			bel[sta[top]]=cnt;ins[sta[top]]=0;top--;

		}

		bel[x]=cnt;--top;ins[x]=0;

	}

}

int main(){

	read(n);read(m);

	for(int i=1,x,y,xx,yy;i<=m;i++){

		read(x);read(xx);read(y);read(yy);

		if(!xx&&!yy){

			add(x,y+n);add(y,x+n);

		}

		if(!xx&&yy){

			add(x,y);add(y+n,x+n);

		}

		if(xx&&yy){

			add(x+n,y);add(y+n,x);

		}

		if(!yy&&xx){

			add(x+n,y+n);add(y,x);

		}

	}

	for(int i=1;i<=n*2;i++){

		if(!dfn[i]) tarjan(i);

	}

	for(int i=1;i<=n;i++){

		if(bel[i]==bel[i+n]){

			puts("IMPOSSIBLE");return 0;

		}

	}

	puts("POSSIBLE");

	for(int i=1;i<=n;i++){

		printf("%d ",bel[i]<bel[i+n]);

	}

	puts("");

	return 0;

}

巴特西

LG4782 「模板」2-SAT问题 2-SAT

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章