题解：P10969 Katu Puzzle

· · 题解

题意

有 n 个点和 m 条边，给每个点赋值为 0 或 1，使得每条边满足 x_i \ \text{op} \ y_i = c_i。

分析

满足 2-sat 模型，这里不做赘述。

考虑建边，对原有边分类讨论：

  1. AND = 1 : x=1,\ y=1
  2. AND = 0 : x=1 \Rightarrow y=0 ,\ y=1 \Rightarrow x=0
  3. OR = 1 : x=0 \Rightarrow y=1 ,\ y=0 \Rightarrow x=1
  4. OR = 0 : x=0,\ y=0
  5. XOR = 0 : x=0 \Leftrightarrow y=1 ,\ x=1 \Leftrightarrow y=0
  6. XOR =1 : x=1 \Leftrightarrow y=1 ,\ x=0 \Leftrightarrow y=0

可以发现对于 2,3,5,6，都是通过一个变量来推导出另一个变量，而对于 1,4，是直接确定了两个变量的值，是本题的一个难点。

考虑 1，发现当 x=0 或 y=0 时一定不能成立，于是新建一个节点 T，让 x=0 和 y=0 连向 T，再让 T 连向所有点。这样，如果推出 x=0 或 y=0，就一定能推出 T，而 T 又能推出所有节点，于是成环。4 同理。

考虑判定有无一组解，先判定 x=0 \Rightarrow x=1 是否成立，如果成立则无解；再判定 x=0 \nRightarrow T 和 x=1 \nRightarrow T 是否至少有一个成立，如果没有则无解（因为如果有一个成立，x 就可以取该值而避免冲突）。

code

#include<bits/stdc++.h>
using namespace std;
const int N=205;
char rdc()
{
    char c=getchar();
    while(c<'A' or c>'Z')c=getchar();
    return c;
}
int rd()
{
    char c=getchar();
    int res=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res;
}
vector<int>g[N];
int n,m,T;
int scc[N],num;
int stk[N],tp;
bool instk[N];
int low[N],dfn[N],inx;
void tar(int x) // tarjan 模板
{
    if(dfn[x])return;
    stk[++tp]=x;
    instk[x]=1;
    low[x]=dfn[x]=++inx;
    for(auto y:g[x])
    {
        if(!dfn[y])
        {
            tar(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y])low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int p;
        num++;
        do{
            p=stk[tp--];
            instk[p]=0;
            scc[p]=num;
        }while(p!=x);
    }
}

signed main()
{
    n=rd();m=rd();
    T=n*2+1;
    for(int i=1;i<=n*2;i++)g[T].push_back(i); // T 通向所有点
    while(m--)
    {
        int x=rd()+1,y=rd()+1,c=rd();
        char op=rdc();
        if(op=='A') // 分类建边
        {
            if(c==1){
                g[x].push_back(T);
                g[y].push_back(T);
            }
            else {
                g[x+n].push_back(y);
                g[y+n].push_back(x);
            }
        }
        else if(op=='O')
        {
            if(c==1){
                g[x].push_back(y+n);
                g[y].push_back(x+n);
            }
            else {
                g[x+n].push_back(T);
                g[y+n].push_back(T);
            }
        }
        else {
            if(c==1){
                g[x].push_back(y+n);
                g[x+n].push_back(y);
                g[y].push_back(x+n);
                g[y+n].push_back(x);
            }
            else {
                g[x].push_back(y);
                g[y].push_back(x);
                g[x+n].push_back(y+n);
                g[y+n].push_back(x+n);
            }
        }
    }
    for(int i=1;i<=n*2+1;i++)tar(i);
    bool fl=1;
    for(int i=1;i<=n;i++)
    {
        if(scc[i]==scc[i+n] or (scc[i]==scc[T] and scc[i+n]==scc[T])) // 判定有无解，见分析 
        {
            fl=0;
            break;
        }
    }
    if(fl)puts("YES");
    else puts("NO");
}