「NowCoder51271」Katu Puzzle 解题报告

$\mathtt{My\ Blog}$

题面

有 $N(1\le N \le 1000)$ 个变量 $X_{1\cdots N}$ ，每个变量的可能取值是 $0$ 或 $1$ ，现有 $M(1\le M\le 10^6)$ 个限制条件，每个条件的形式为：

$X_i\ op \ X_j=c,c\in \{0,1\},op\in\{and,or,xor\}$
求是否有合法的方案，使所有条件成立，输出 YES 或 NO

解题思路

$2-SAT\&SCC$

分析

每个变量只有两种选择，明显是一个 $2-SAT$ 问题模板，考虑如何建图

对于每种 $op$ 分情况讨论：

$x\ and\ y=0$
考虑什么时候需要限制，显然，当 $x,y$ 两者有一个为 $1$ 时，另一个必为 $0$
因此建立有向边： $x+n\to y,y+n\to x$
$x\ and\ y=1$
仍然考虑什么时候需要限制，显然， $x,y$ 都必须为 $1$ ，也就是 $x,y$ 都不能为 $0$
直接让两者同时不满足即可，因此建有向边： $x\to x+n,y\to y+n$ ，显然 $x,y$ 为 $0$ 时，上述条件无法满足
$x \ or \ y=0$
$x,y$ 都必须为 $0$ ，与情况 2 类似，建有向边： $x+n\to x,y+n\to y$
$x\ or\ y=1$
与 1 类似，建立有向边： $x\to y+n,y\to x+n$
$x\ xor\ y=0$
$x,y$ 的值必须相同，建有向边： $x\to y,y\to x,x+n\to y+n,y+n\to x+n$
$x\ xor\ y=1$
$x,y$ 的值必须不同，建有向边： $x\to y+n,y\to x+n,y+n\to x,x+n\to y$

总结即为：

$x\ and\ y=0$
$x+n\to y,y+n\to x$
$x\ and\ y=1$
$x\to x+n,y\to y+n$
$x \ or \ y=0$
$x+n\to x,y+n\to y$
$x\ or\ y=1$
$x\to y+n,y\to x+n$
$x\ xor\ y=0$
$x\to y,y\to x,x+n\to y+n,y+n\to x+n$
$x\ xor\ y=1$
$x\to y+n,y\to x+n,y+n\to x,x+n\to y$

之后用 $tarjan$ 求出 $SCC$ 判断是否存在 $i$ ，使得 $i,i+n$ 在同一个强连通分量内即可

Warning

1、边的数量上限为条件数的四倍

2、变量的下标从 $0$ 开始

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 1000003
#define N 1003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline char getc() {//读个操作，个人爱好而已
    rgt char c=getchar();
    while(c<'A'||c>'Z') c=getchar();
    return c;
}
int head[N<<1],ver[M<<2],nxt[M<<2],t,n,m,res;//边开四倍
int dfn[N<<1],low[N<<1],bl[N<<1],St[N<<1],top,num;//其余开两倍
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t;
}
inline void tarjan(rint k) {
    rint i,to;
    dfn[k]=low[k]=++num,St[++top]=k;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(!dfn[to]) tarjan(to),cmin(low[k],low[to]);
        else if(!bl[to]) cmin(low[k],dfn[to]);
    }
    if(dfn[k]==low[k]) {
        bl[k]=++res;
        while(St[top]!=k)
            bl[St[top--]]=res;
        --top;
    }
}
int main()
{
    rint i,x,y,c;char op;
    n=read(),m=read();
    for(i=1;i<=m;i++) {
        x=read()+1,y=read()+1,//下标+1，不加影响不大（个人喜好
        c=read(),op=getc();
        if(op=='A') {//分情况加边
            if(c) add(x,x+n),add(y,y+n);
            else add(x+n,y),add(y+n,x);
        }
        else if(op=='O') {
            if(c) add(x,y+n),add(y,x+n);
            else add(x+n,x),add(y+n,y);
        }
        else {
            if(c) add(x,y+n),add(y,x+n),add(x+n,y),add(y+n,x);
            else add(x,y),add(y,x),add(x+n,y+n),add(y+n,x+n);
        }
    }
    for(i=1;i<=(n<<1);i++)
        if(!dfn[i]) tarjan(i);
    for(i=1;i<=n;i++) 
        if(bl[i]==bl[i+n]) {//在同一个强连通分量内就无解
        printf("NO");return 0;
    }
    printf("YES");
    return 0;
}