首页 > 代码库 > hdu 4421 BitMagic

hdu 4421 BitMagic

2024-07-08 21:33:12   221人阅读

这是一道区域赛的题目，解法有许多，这边是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=0104                         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 }
View Code

 


联系
我们