当前位置：首页 > news >正文

hdu 4421 BitMagic

news 来源：原创 2024/5/6 3:26:12

这是一道区域赛的题目，解法有许多，这边是2-sat的做法

题目大意:自己看题

分析：对于A[i]的每一位做2-SAT，判断是否可行。

主要是建图：

对于a&b=0 有 a-> ┐b, b-> ┐a

a&b=1 ┐a->a , ┐b->b

a|b=0 a-> ┐a,b-> ┐b

a|b=1　　　 ┐a->b, ┐b->a

a^b=0　　　　a->b,b->a, ┐a-> ┐b, ┐b-> ┐a

a^b=1　　　　a-> ┐b,b-> ┐a, ┐a->b, ┐b->a

用Kosaraju算法会T(也许我写渣了)用Tarjan算法就ok╮(╯▽╰)╭

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <set>
  5 #include <algorithm>
  6 #include <map>
  7 #include<vector>
  8 using namespace std;
  9 const int MAXN = 2010;
 10 const int MAXM = 1010*501*2;
 11 struct Edge
 12 {
 13     int to,next;
 14 } edge[MAXM];
 15 int head[MAXN],tot;
 16 void addedge(int u,int v)
 17 {
 18     edge[tot].to = v;
 19     edge[tot].next = head[u];
 20     head[u] = tot++;
 21 }
 22 int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值1~scc
 23 int Index,top;
 24 int scc;
 25 bool Instack[MAXN];
 26 int num[MAXN];
 27 void init()
 28 {
 29     tot = 0;
 30     memset(head,-1,sizeof(head));
 31 }
 32 void Tarjan(int u)
 33 {
 34     int v;
 35     Low[u] = DFN[u] = ++Index;
 36     Stack[top++] = u;
 37     Instack[u] = true;
 38     for(int i = head[u]; i != -1; i = edge[i].next)
 39     {
 40         v = edge[i].to;
 41         if( !DFN[v] )
 42         {
 43             Tarjan(v);
 44             if(Low[u] > Low[v])Low[u] = Low[v];
 45         }
 46         else if(Instack[v] && Low[u] > DFN[v])
 47             Low[u] = DFN[v];
 48     }
 49     if(Low[u] == DFN[u])
 50     {
 51         scc++;
 52         do
 53         {
 54             v = Stack[--top];
 55             Instack[v] = false;
 56             Belong[v] = scc;
 57             num[scc]++;
 58         }
 59         while(v != u);
 60     }
 61 }
 62 int maps[1010][1010];
 63 bool solve(int m){
 64     for(int i=0;i<m;++i){
 65         for(int j=0;j<m;++j){
 66             if(i==j&&maps[i][j])return false;
 67             if(maps[i][j]!=maps[j][i])return false;
 68         }
 69     }
 70     for(int k=0;k<31;++k){
 71         init();
 72         for(int i=0;i<m;++i){
 73             for(int j=0;j<m;++j){
 74                 if(i==j)continue;
 75                 int is = maps[i][j]&(1<<k);
 76                 if((i&1)&&(j&1)){//|
 77                     if(is){//a|b=1
 78                         addedge(i,j+m);
 79                         addedge(j,i+m);
 80                     }
 81                     else{//a|b=0
 82                         addedge(i+m,i);
 83                         addedge(j+m,j);
 84                     }
 85                 }
 86                 else if((i%2==0)&&(j%2==0)){//&
 87                     if(is){//a&b=1
 88                         addedge(i,i+m);
 89                         addedge(j,j+m);
 90                     }
 91                     else{//a&b=0
 92                         addedge(i+m,j);
 93                         addedge(j+m,i);
 94                     }
 95                 }
 96                 else {//^
 97                     if(is){//a^b=1
 98                         addedge(i+m,j);
 99                         addedge(j+m,i);
100                         addedge(i,j+m);
101                         addedge(j,i+m);
102                     }
103                     else{//a^b=0
104                         addedge(i+m,j+m);
105                         addedge(j+m,i+m);
106                         addedge(i,j);
107                         addedge(j,i);
108 
109                     }
110                 }
111             }
112         }
113         memset(DFN,0,sizeof(DFN));
114         for(int i=0;i<2*m;++i){
115             if(!DFN[i])Tarjan(i);
116         }
117         for(int i=0;i<m;++i){
118             if(Belong[i]==Belong[m+i]){
119                 return false;
120             }
121         }
122     }
123     return true;
124 }
125 int main (){
126     int m;
127     while(scanf("%d",&m)!=EOF){
128         for(int i=0;i<m;++i){
129             for(int j=0;j<m;++j){
130                 scanf("%d",&maps[i][j]);
131             }
132         }
133         if(solve(m))printf("YES\n");
134         else printf("NO\n");
135     }
136 }