网站建设找丿金手指排名,在百度做网站怎么做,网站解析教程,网站界面ui设计正题
题目链接:http://poj.org/problem?id3678 题目大意 nnn个xix_ixi为0/10/10/1。有mmm个条件表示xiandxjax_i\ and\ x_jaxi and xja或xiorxjax_i\ or\ x_jaxi or xja或xixorxjax_i\ xor\ x_jaxi xor xja。 求构造一组合法的xix_ixi。 解题思路
讨论一下 …正题
题目链接:http://poj.org/problem?id3678 题目大意
nnn个xix_ixi为0/10/10/1。有mmm个条件表示xiandxjax_i\ and\ x_jaxi and xja或xiorxjax_i\ or\ x_jaxi or xja或xixorxjax_i\ xor\ x_jaxi xor xja。 求构造一组合法的xix_ixi。 解题思路
讨论一下
xiandxj0:x_i\ and\ x_j0:xi and xj0:xix_ixi和xjx_jxj不都是111也就是xix_ixi为111那么xjx_jxj必须为0反之xiandxj1:x_i\ and\ x_j1:xi and xj1:xix_ixi和xjx_jxj都是111这时候我们就构造矛盾条件xi0x_i0xi0则xi1x_i1xi1限制xi0x_i0xi0即可xjx_jxj同xiorxj0:x_i\ or\ x_j0:xi or xj0:xix_ixi和xjx_jxj都是000和上面222一样构造即可xiorxj1:x_i\ or\ x_j1:xi or xj1:xix_ixi和xjx_jxj不都是000和上面111一样构造即可xixorxj0:x_i\ xor\ x_j0:xi xor xj0:那么xi0⇒xj0x_i0\Rightarrow x_j0xi0⇒xj0且xi1⇒xj1x_i1\Rightarrow x_j1xi1⇒xj1反之xixorxj1:x_i\ xor\ x_j1:xi xor xj1:那么xi0⇒xj1x_i0\Rightarrow x_j1xi0⇒xj1且xi1⇒xj0x_i1\Rightarrow x_j0xi1⇒xj0反之
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N2100;
struct node{int to,next;
}a[N*4000];
int n,m,tot,num,cnt,ls[N];
int dfn[N],low[N],color[N];
bool ins[N];
stackint S;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void tarjan(int x){dfn[x]low[x]cnt;ins[x]1;S.push(x);for(int ils[x];i;ia[i].next){int ya[i].to;if(!dfn[y])tarjan(y),low[x]min(low[x],low[y]);else if(ins[y])low[x]min(low[x],dfn[y]);}if(dfn[x]low[x]){num;while(S.top()!x){color[S.top()]num;ins[S.top()]0;S.pop();}color[S.top()]num;ins[S.top()]0;S.pop();}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int a,b,w;char op[4];scanf(%d %d %d %s,a,b,w,op);if(op[0]A){if(w)addl(a,an),addl(b,bn);else addl(bn,a),addl(an,b);}if(op[0]O){if(w)addl(b,an),addl(a,bn);else addl(an,a),addl(bn,b);}if(op[0]X){if(w)addl(a,bn),addl(b,an),addl(an,b),addl(bn,a);else addl(a,b),addl(b,a),addl(an,bn),addl(bn,an);}}for(int i0;i2*n;i)if(!dfn[i])tarjan(i);for(int i0;in;i)if(color[i]color[in]){printf(NO\n);return 0;}printf(YES\n);return 0;
}
