hdu4115

题解：

2-sat

对于bob出的每一张牌，alice显然只有两种选择

然后对于每一个限制，连边

判断是否可行

代码：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int flag[N],ans,T,cas,m,x,y,kkk,k,l,n;

int ne[N],fi[N],a[N],b[N],zz[N],num,t,zhan[N],dfn[N],low[N],an[N];

void init()

{

    printf("Case #%d: ",++cas);

    kkk=;num=l=;

    memset(fi,,sizeof fi);

    memset(an,,sizeof an);

    memset(dfn,,sizeof dfn);

}

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!=;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",&T);

    while (T--)

     {

         init();

         scanf("%d%d",&n,&m);

         for (int i=;i<n;i++)

          {

              scanf("%d",&x);x--;

              a[i]=x;a[i+n]=(x+)%;

          }

         while (m--)

         {

             scanf("%d%d%d",&x,&y,&k);

             x--;y--;

             if (k==)

              {

                 if (a[x]!=a[y+n])jb(x,y),jb(y+n,x+n);

                  if (a[x]!=a[y])jb(x,y+n),jb(y,x+n);

                  if (a[x+n]!=a[y+n])jb(x+n,y),jb(y+n,x);

                  if (a[x+n]!=a[y])jb(x+n,y+n),jb(y,x);

              }

             else

             {

                 if (a[x]==a[y+n])jb(x,y),jb(y+n,x+n);

                  if (a[x]==a[y])jb(x,y+n),jb(y,x+n);

                  if (a[x+n]==a[y+n])jb(x+n,y),jb(y+n,x);

                  if (a[x+n]==a[y])jb(x+n,y+n),jb(y,x);

             }

         }

        for (int i=;i<*n;i++)

         if (!dfn[i])dfs(i);

        for (int i=;i<n;i++)

         if (an[i]==an[i+n])

          {

              puts("no");

              kkk=;

              break;

          }

        if (kkk)puts("yes");

     }

}