题目描述
有n个布尔变量x_1x1~x_nxn，另有m个需要满足的条件，每个条件的形式都是“x_ixi为true/false或x_jxj为true/false”。比如“x_1x1为真或x_3x3为假”、“x_7x7为假或x_2x2为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
输入输出格式
输入格式：
第一行两个整数n和m，意义如体面所述。
接下来m行每行4个整数 i a j b，表示“x_ixi为a或x_jxj为b”(a,b∈{0,1})
输出格式：
如无解，输出“IMPOSSIBLE”（不带引号）; 否则输出"POSSIBLE"（不带引号),下 一行n个整数x_1x1~x_nxn（x_ixi∈{0,1}），表示构造出的解。
#include#define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)using namespace std;const int maxn=1e6+10;template inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9'){ ret = ret * 10 + (c - '0'), c = getchar(); }}struct node{ int to,nx;}p[maxn<<2];int n,m,head[maxn<<1],sk[maxn<<1],dfn[maxn<<1],low[maxn<<1],tot,cur,now,nc,scc[maxn<<1],hs[maxn<<1],link;void addedge(int u,int v){ p[++tot].to=v,p[tot].nx=head[u],head[u]=tot;}void tarjan(int rt){ dfn[rt]=low[rt]=++now; sk[nc++]=rt; hs[rt]=1; for(int i=head[rt];i;i=p[i].nx){ if(!dfn[p[i].to]){ tarjan(p[i].to); low[rt]=min(low[rt],low[p[i].to]); } else if(hs[p[i].to])low[rt]=min(low[rt],dfn[p[i].to]); } if(low[rt]==dfn[rt]){ int curv; link++; do{ curv=sk[--nc]; hs[curv]=0; scc[curv]=link; }while(rt!=curv); }}int solve(){ for(int i=1;i<=2*n;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ if(scc[i]==scc[i+n])return 0; } return 1;}int main(){ scanf("%d%d",&n,&m); REP(i,1,m){ int l,vl,r,vr; scanf("%d%d%d%d",&l,&vl,&r,&vr); int revl=vl^1,revr=vr^1; addedge(l+n*revl,r+n*vr); addedge(r+n*revr,l+n*vl); } if(!solve()){ printf("IMPOSSIBLE"); } else{ printf("POSSIBLE\n"); for(int i=1;i<=n;i++){ if(scc[i]>scc[i+n])printf("1 "); else printf("0 "); } } return 0;}
输入输出样例
输入样例#1：
3 11 1 3 0
输出样例#1：
POSSIBLE0 0 0
说明
1<=n,m<=1e6 , 前3个点卡小错误，后面5个点卡效率，由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。