hdu 4421 BitMagic-白红宇

hdu 4421 BitMagic

阅读量：6116 次

发布时间：2019-06-21

本文共 1592 字，大约阅读时间需要 5 分钟。

这是一道区域赛的题目，解法有许多，这边是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 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
            7 #include
            
              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