欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj3678 Katu Puzzle

程序员文章站 2022-04-28 14:19:03
题意 给定一张图,对于每条边给出一个运算符$(\&,|,\otimes)$和一个值$c(0 \le c \le 1)$。问能否 ......

题意

给定一张图,对于每条边给出一个运算符\((\&,|,\otimes)\)和一个值\(c(0 \le c \le 1)\)。问能否通过给每个点赋上一个值。使得每条边通过指定的运算都能得到指定的值。

思路

\(2-sat\)问题,需要注意的是当两数\(\&\)起来为\(1\)时。必须全部为\(1\),所以就从每个点的\(0\)\(1\)连边。同理,当两数\(|\)起来为\(0\)时,必须全部为\(0\),所以就从每个点的\(1\)\(0\)连边。

代码

/*
* @author: wxyww
* @date:   2019-04-27 16:42:24
* @last modified time: 2019-04-27 17:09:58
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 3000 + 10,m = 5000000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[m];
int head[n],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
char s[5];
int sta[n],dfn[n],top,coljs,cnt,vis[n],low[n],col[n];
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    sta[++top] = u;
    vis[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(vis[v]) low[u] = min(low[u],low[v]);
    }
    if(low[u] == dfn[u]) {
        ++coljs;
        do {
            int x = sta[top--];
            col[x] = coljs;
            vis[x] = 0;
        }while(sta[top + 1] != u);
    }
}
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= m;++i) {
        int u = read() + 1,v = read() + 1,w = read();
        scanf("%s",s + 1);
        if(s[1] == 'o') {
            if(w)   add(u,v + n),add(v,u + n);
            else  add(u + n,u),add(v + n,v);
        }
        else if(s[1] == 'x') {
            if(w) add(u,v + n),add(u + n,v),add(v + n,u),add(v,u + n);
            else add(u,v),add(u + n,v + n),add(v,u),add(v + n,u + n);
        }
        else {
            if(w) add(u,u + n),add(v,v + n);
            else add(u + n,v),add(v + n,u);
        }
    }
    for(int i = 1;i <= n + n;++i) if(!dfn[i]) tarjan(i);
    for(int i = 1;i <= n;++i) {
        if(col[i] == col[i + n]) {
            puts("no");return 0;
        }
    }
    puts("yes");
    return 0;
}