zoj3656长春B

gistfile1.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 1110
#define MM 11100000


int n,i,j,b[NN][NN],flag,bit;
int first[NN],next[MM],v[MM],tote;
int totb,top,totdfn,dfn[NN],low[NN],block[NN],ins[NN],sta[NN];


inline void addedge(int x,int y){
    next[++tote]=first[x];
    first[x]=tote;
    v[tote]=y;
}

void tarjan(int u){
     
     dfn[u]=low[u]=++totdfn;
     sta[++top]=u;
     ins[u]=1;
     int e,vv;
     for(e=first[u];e!=-1;e=next[e]){
          vv=v[e];
          if (!dfn[vv]){
               tarjan(vv);
               if (low[vv]<low[u]) low[u]=low[vv];
          }
          else if (ins[vv]&&dfn[vv]<low[u]) low[u]=dfn[vv];
     }
     if (low[u]==dfn[u]){
          ++totb;
          do{
             vv=sta[top--];
             ins[vv]=0;
             block[vv]=totb;
          }while(vv!=u);
     }
}


void scc(){
     memset(ins,0,sizeof(ins));
     memset(dfn,0,sizeof(dfn));
     totb=top=totdfn=0;
     int i;
     for(i=0;i<2*n;i++)if (!dfn[i]){
       tarjan(i);
     }
}
     
int solve(int bit){
    memset(first,-1,sizeof(first));
    tote=0;
    int i,j;
    int kk=1<<(bit-1);
    for(i=0;i<n;i++){                   //make graph
      for(j=0;j<n;j++){
          //if (bit==5)printf("%d %d %d %d %d\n",i,j,i&1,j&1,b[i][j]&kk);
          if (i==j) {if (b[i][j]) return 0;}
          else if ((i&1)&&(j&1)){
               if (b[i][j]&kk){
                    addedge(i,j+n);
                    addedge(j,i+n);
               }
               else{
                   addedge(i+n,i);
                   addedge(j+n,j);
               }
          }
          else if (((i&1)==0)&&((j&1)==0)){
               if (b[i][j]&kk){
                    addedge(i,i+n);
                    addedge(j,j+n);
               }
               else {
                    addedge(i+n,j);
                    addedge(j+n,i);
               }
          }
          else {
               if (b[i][j]&kk){
                    addedge(i,j+n);
                    addedge(j,i+n);
                    addedge(i+n,j);
                    addedge(j+n,i);
               }
               else {
                    addedge(i,j);
                    addedge(j,i);
                    addedge(i+n,j+n);
                    addedge(j+n,i+n);
               }
          }
     }
   }
   //printf("333\n");
   scc();
   for(i=0;i<n;i++){
       if (block[i]==block[i+n]){return 0;}
   }
   return 1;
}
                    


int main(){
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++){
          for(j=0;j<n;j++){
             scanf("%d",&b[i][j]);
          }
        }
        flag=1;
        for(i=0;i<n;i++) if (b[i][i]!=0) {flag=0;break;}
        if (flag==0) {puts("NO");continue;}
        
        
        for(bit=1;bit<=31;bit++){
            //printf("%d\n",bit);
            if (!solve(bit)) {flag=0;break;}
            
        }
        
        if (flag==0) puts("NO");
        else puts("YES");
    }
    return 0;
}