首页 > 学院 > 开发设计 > 正文

[POJ3678] Katu Puzzle

2019-11-06 06:49:04
字体:
来源:转载
供稿:网友

题目

给出a,b,v三个整数和ope字符串 询问是否存在一组{xi},xi={0,1}满足所有的xa ope xb=v ope取值“AND”“OR”“XOR”

题解

经典的2-SAT问题 题解

代码

/// by ztx/// blog.csdn.net/hzoi_ztx/// [poj] 3678: Katu Puzzle/// submit with G++#include <cstdio>#define Rep(i,l,r) for(i=(l);i<=(r);i++)#define Rev(i,r,l) for(i=(r);i>=(l);i--)#define maxe 4000100LL#define maxn 5000LLstruct FST { int to , next ; } e[maxe];int star[maxn] = {0}, tote = 1;inline void AddEdge(int u , int v) { e[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ; }int DFN[maxn] = {0};int LOW[maxn] = {0};int sta[maxn] = {0}, top = 0;bool insta[maxn] = {0};int belong[maxn] = {0};int idx = 0, cntblc = 0;void dfs(int u) {int v, p; DFN[u] = LOW[u] = ++idx; sta[++top] = u, insta[u] = true; for (p=star[u];p;p=e[p].next) { if (!DFN[v=e[p].to]) { dfs(v); if (LOW[u] > LOW[v]) LOW[u] = LOW[v]; } else if (insta[v] && LOW[u]>DFN[v]) LOW[u] = DFN[v]; } if (LOW[u] == DFN[u]) for (cntblc++ ; u!=v ; ) { insta[v=sta[top]] = false; belong[v] = cntblc; top -- ; }}int n , m ;int main() {int i, a, b, w; scanf("%d%d", &n, &m) ; char ope[10]; Rep (i,1,m) { scanf("%d%d%d%s", &a, &b, &w, ope); if (ope[0] == 'A') { if (w) { AddEdge(a+n,b+n); AddEdge(b+n,a+n); AddEdge(a,a+n); AddEdge(b,b+n); } else { AddEdge(a+n,b); AddEdge(b+n,a); } } else if (ope[0] == 'O') { if (w) { AddEdge(a,b+n); AddEdge(b,a+n); } else { AddEdge(a,b); AddEdge(b,a); AddEdge(a+n,a); AddEdge(b+n,b); } } else if (ope[0] == 'X') { if (w) { AddEdge(a,b+n); AddEdge(b,a+n); AddEdge(a+n,b); AddEdge(b+n,a); } else { AddEdge(a,b); AddEdge(b,a); AddEdge(a+n,b+n); AddEdge(b+n,a+n); } } } //Tarjan Rep (i,0,n*2-1) if (!DFN[i]) dfs(i); Rep (i,0,n-1) if (belong[i] == belong[i+n]){ puts("NO"); goto END; } puts("YES"); END : getchar(), getchar(); return 0 ;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表