题解:
2-sat问题
构图十分巧妙
具体可以看我的代码的构图部分
代码:
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N=2005; char s[5]; int flag[N],x,y,z,n,ne[N*N],fi[N],zz[N*N],num; int t,zhan[N],dfn[N],m,l,ans,low[N],an[N]; void jb(int x,int y) { ne[++num]=fi[x]; fi[x]=num; zz[num]=y; } void dfs(int x) { low[x]=dfn[x]=++l; zhan[++t]=x; flag[x]=true; for (int i=fi[x];i!=0;i=ne[i]) { if (an[zz[i]])continue; if(!dfn[zz[i]])dfs(zz[i]); if(!flag[zz[i]])low[x]=min(low[x],dfn[zz[i]]);else low[x]=min(low[x],low[zz[i]]); } if (dfn[x]==low[x]) { ans++; while (zhan[t]!=x) { flag[zhan[t]]=false; an[zhan[t--]]=ans; } an[zhan[t--]]=ans; flag[x]=false; } } int main() { scanf("%d%d",&n,&m); while (m--) { scanf("%d%d%d%s",&x,&y,&z,&s); if (s[0]=='A'&&z==0)jb(x+n,y),jb(y+n,x); if (s[0]=='A'&&z==1)jb(x,x+n),jb(y,y+n); if (s[0]=='O'&&z==0)jb(x+n,x),jb(y+n,y); if (s[0]=='O'&&z==1)jb(x,y+n),jb(y,x+n); if (s[0]=='X'&&z==0)jb(x+n,y+n),jb(x,y),jb(y+n,x+n),jb(y,x); if (s[0]=='X'&&z==1)jb(x+n,y),jb(x,y+n),jb(y+n,x),jb(y,x+n); } for (int i=0;i<2*n;i++) if (!dfn[i])dfs(i); for (int i=0;i<n;i++) if (an[i]==an[i+n]) { puts("NO"); return 0; } puts("YES"); return 0; }