題目鏈接：點(diǎn)擊查看

題目大意：給出n個(gè)數(shù)字，以及m個(gè)關(guān)系，每個(gè)關(guān)系只可能是xor、and或or其中之一，問能否有一種賦值滿足所有m個(gè)關(guān)系

題目分析：2-SAT模板題，因?yàn)槊總€(gè)關(guān)系中的a和b都有一定的關(guān)系，比如a and b=0，就要求a和b中至少有一個(gè)數(shù)為0，換句話說，如果a為1，那么b必定為0，反過來也是一樣，若b為1，則a也必定為0，形如這樣的關(guān)系我們就可以利用2-SAT建邊，然后強(qiáng)連通縮點(diǎn)，如果保證所有的點(diǎn)拆成的兩個(gè)點(diǎn)都不屬于同一個(gè)強(qiáng)連通集合中，就說明題目有解，否則無解，建邊方法如下：

AND：

a and b = 1

a->a+n

b->b+n

a and b = 0

a+n->a

b+n->b

OR：

a or b = 1

a->b+n

b->a+n

a or b = 0

a+n->a

b+n->b

XOR：

a xor b = 1

a->b+n

b->a+n

a+n->b

b+n->a

a xor b = 0

a->b

b->a

a+n->b+n

b+n->a+n

最后注意一下，這個(gè)題目中的點(diǎn)是從0點(diǎn)開始的，記得稍微修改一下tarjan的for循環(huán)范圍就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e3+100;const int M=4e6+100;struct Egde {int to,next; }edge1[M];int head1[N],low[N],dfn[N],c[N],Stack[N],num,cnt,cnt1,dcc,n,m,top;bool ins[N];vector<int>scc[N];void addedge1(int u,int v) {edge1[cnt1].to=v;edge1[cnt1].next=head1[u];head1[u]=cnt1++; }void tarjan(int u) {dfn[u]=low[u]=++num;Stack[++top]=u;ins[u]=true;for(int i=head1[u];i!=-1;i=edge1[i].next){int v=edge1[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){cnt++;int v;do{v=Stack[top--];ins[v]=false;c[v]=cnt;scc[cnt].push_back(v);}while(u!=v);} }void solve() {for(int i=0;i<2*n;i++)//縮點(diǎn) if(!dfn[i])tarjan(i); }void init() {for(int i=0;i<N;i++)scc[i].clear();top=cnt=cnt1=num=dcc=0;memset(head1,-1,sizeof(head1));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(c,0,sizeof(c));memset(ins,false,sizeof(ins)); }bool check() {for(int i=0;i<n;i++)if(c[i]==c[i+n])return false;return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){init();while(m--){int a,b,c;char s[10];scanf("%d%d%d%s",&a,&b,&c,s);if(s[0]=='A'){if(c)//a and b = 1{addedge1(a,a+n);addedge1(b,b+n);}else//a and b = 0{addedge1(a+n,b);addedge1(b+n,a);}}else if(s[0]=='O'){if(c)//a or b = 1{addedge1(a,b+n);addedge1(b,a+n);}else//a or b = 0{addedge1(a+n,a);addedge1(b+n,b);}}else if(s[0]=='X'){if(c)//a xor b = 1{addedge1(a,b+n);addedge1(b,a+n);addedge1(a+n,b);addedge1(b+n,a);}else//a xor b = 0{addedge1(a,b);addedge1(b,a);addedge1(a+n,b+n);addedge1(b+n,a+n);}}}solve();if(check())puts("YES");elseputs("NO");} return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3678 Katu Puzzle(2-SAT)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。