//2-sat
//适用于点集成对给出,最多只能取其中一个。
//poj3678
//建图: 0..n-1取0; n..2n-1取1
//连接某边是为了推出矛盾。x->y表示选x则必须选y
//求一次极大连通子图,判断id[i]==id[i+n]这个矛盾是否成立既可。
//n=1000在poj大约需要400+ms。算法复杂度为O(n^2)
#include <string.h>
#include <stdio.h>
#define MAXN 2100
int find_components(int n,int mat[][MAXN],int* id){
int ret=0,a[MAXN],b[MAXN],c[MAXN],d[MAXN],i,j,k,t;
for (k=0;k<n;id[k++]=0);
for (k=0;k<n;k++)
if (!id[k]){
for (i=0;i<n;i++)
a[i]=b[i]=c[i]=d[i]=0;
a[k]=b[k]=1;
for (t=1;t;)
for (t=i=0;i<n;i++){
if (a[i]&&!c[i])
for (c[i]=t=1,j=0;j<n;j++)
if (mat[i][j]&&!a[j])
a[j]=1;
if (b[i]&&!d[i])
for (d[i]=t=1,j=0;j<n;j++)
if (mat[j][i]&&!b[j])
b[j]=1;
}
for (ret++,i=0;i<n;i++)
if (a[i]&b[i])
id[i]=ret;
}
return ret;
}
int id[MAXN],mat[MAXN][MAXN];
void addedge(int a,int b){
mat[a][b]=1;
}
int main(){
int n,m,i,j,k,x,y,a,b,c;
char op[8];
scanf("%d %d",&n,&m);
memset(mat,0,sizeof(mat));
memset(id,0,sizeof(id));
for (i=0;i<m;i++){
scanf("%d %d %d %s",&a,&b,&c,op);
if (op[0]=='A'){
if (c==1){
mat[a][a+n]=mat[b][b+n]=1;
mat[a+n][b+n]=mat[b+n][a+n]=1;
}
else{
mat[a+n][b]=mat[b+n][a]=1;
}
}
if (op[0]=='O'){
if (c==1){
mat[a][b+n]=mat[b][a+n]=1;
}
else{
mat[a+n][a]=mat[b+n][b]=1;
mat[a][b]=mat[b][a]=1;
}
}
if (op[0]=='X'){
if (c==1){
mat[a][b+n]=mat[b][a+n]=1;
mat[a+n][b]=mat[b+n][a]=1;
}
else{
mat[a][b]=mat[b][a]=1;
mat[a+n][b+n]=mat[b+n][a+n]=1;
}
}
}
find_components(2*n,mat,id);
int ans=1;
for (i=0;i<n;i++){
if (id[i]==id[i+n]) ans=0;
// printf("node=%d id=%d node'=%d id=%d\n",i,id[i],i+n,id[i+n]);
}
if (ans==1) printf("YES\n");else printf("NO\n");
}
评论0