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; }
上一篇: 4.JAVA-数组、String详解