zoj3656

题解：

按照位展开，然后一位一位判断

注意判断给出数据是否有问题

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1005;
int flag[N],n,b[N][N],ne[2*N*N],fi[N],zz[4*N*N],num;
int t,zhan[N],dfn[N],m,l,q,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;
     }
}
void init()
{
    ans=num=l=0;
    memset(fi,0,sizeof fi);
    memset(an,0,sizeof an);
    memset(dfn,0,sizeof dfn);
}
int main()
{
    while (~scanf("%d",&n))
     {
        for (int i=0;i<n;i++)
         for (int j=0;j<n;j++)scanf("%d",&b[i][j]);
        q=0; 
        for (int i=0;i<n;i++)
         if (b[i][i])q=1;
        for (int i=0;i<n;i++)
         for (int j=0;j<n;j++)
          if (b[i][j]!=b[j][i])q=1; 
        for (int k=0;k<31;k++)
         {
             init();
             for (int i=0;i<n;i++)
              for (int j=i+1;j<n;j++)
               {
                   int c=b[i][j]&(1<<k);
                   if (i%2==1&&j%2==1)
                    {
                        if (c==0)
                         {
                             jb(i+n,i);
                             jb(j+n,j);
                         }
                        else
                         {
                             jb(i,j+n);
                             jb(j,i+n);
                         } 
                    }
                   else if (i%2==0&&j%2==0)
                 {
                     if (c==0)
                      {
                          jb(i+n,j);
                          jb(j+n,i);
                      }
                     else
                     {
                         jb(i,i+n);
                         jb(j,j+n);
                     } 
                 }
                else
                 {
                     if (c==0)
                      {
                          jb(i,j);
                          jb(i+n,j+n);
                          jb(j,i);
                          jb(j+n,i+n);
                      }
                     else
                     {
                         jb(i,j+n);
                         jb(i+n,j);
                         jb(j,i+n);
                         jb(j+n,i);
                     } 
                 } 
               }
             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])q=1;
             if (q)break;  
         }
        if (!q)puts("YES");
        else puts("NO"); 
     }
    return 0; 
}