「NowCoder51271」Katu Puzzle 解题报告

题面

有 个变量 ，每个变量的可能取值是 或 ，现有 个限制条件，每个条件的形式为：

求是否有合法的方案，使所有条件成立，输出 YES 或 NO

解题思路

分析

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

对于每种 分情况讨论：

1. 
   考虑什么时候需要限制，显然，当 两者有一个为 时，另一个必为
   因此建立有向边：
2. 
   仍然考虑什么时候需要限制，显然， 都必须为 ，也就是 都不能为
   直接让两者同时不满足即可，因此建有向边：，显然 为 时，上述条件无法满足
3. 
   都必须为 ，与情况 2 类似，建有向边：
4. 
   与 1 类似，建立有向边：
5. 
   的值必须相同，建有向边：
6. 
   的值必须不同，建有向边：

总结即为：

之后用 求出 判断是否存在 ，使得 在同一个强连通分量内即可

Warning

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

2、变量的下标从 开始

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;
}