hdu4421 2-sat(枚舉二進制每一位)

題意：

      給你一個數組b[][],在給你一些關系，問是否可以找到一個滿足限制的a[],

關系如下（圖檔）：

思路：

      說到限制，而且還是兩個兩個之間的限制，那麼很容易想到2-sat但是這個題目

紮一看還不像，b[i][j]不是隻 0 1 2，怎麼辦呢，其實我們可以一位一位枚舉，最多

也就32，對于每一位我們都判斷下，隻有所有的位數都滿足了，才算存在a[]，下面說下關鍵，就是怎麼建圖。

a[i] | a[j] == 0 說明兩個都是0,則           a  ~a ,b ~b.

a[i] | a[j] == 1 說明兩個至少有一個是1則    ~a  b ,~b a.

a[i] & a[j] == 1 說明兩個都是1，則          ~a  a ,~b b.

a[i] & a[j] == 0 說明至少有一個0 則         b ~a  ,a ~b.

a[i] ^ a[j] == 1 說明兩個不同 則            a ~b ,b ~a ,~a b ,~b a

a[i] ^ a[j] == 0 說明兩個相同 則            a b ,b ,a ,~a ~b ,~b ~a

然後強連通判斷是否可行就行了，這裡說一下，之前我強連通用的全是雙深搜的那個，一直都可以，知道今天這個題目一直逾時，我一開始想不出逾時的地方，隻能是換了個強連通的算法，用的Tarjan結果1625ms AC了.蛋疼。

#include<stdio.h>
#include<string.h>
#include<stack>

#define N_node 1000 + 50
#define N_edge 1000000 + 100

using namespace std;

typedef struct
{
        int to ,next;
}STAR;

STAR E[N_edge];
int list[N_node] ,tot;
int DFN[N_node] ,LOW[N_node];
int Belong[N_node];
int Index ,num ,okk;
int instack[N_node];
int B[550][550];
stack<int>st; 

void add(int a ,int b)
{
   E[++tot].to = b;
   E[tot].next = list[a];
   list[a] = tot;
}

int minn(int x ,int y)
{
   return x < y ? x : y;
}

void Tarjan(int s)
{
   DFN[s] = LOW[s] =  Index ++;
   st.push(s);
   instack[s] = 1;
   for(int k = list[s] ;k ;k = E[k].next)
   {
      int to = E[k].to;
      if(!DFN[to])
      {
         Tarjan(to);
         LOW[s] = minn(LOW[to] ,LOW[s]);
      }
      else if(instack[to])
      {
         LOW[s] = minn(DFN[to] ,LOW[s]);    
      }
   }
   if(LOW[s] == DFN[s])
   {
      num ++; 
      while(1)
      {
         int v = st.top();
         Belong[v] = num;
         st.pop();
         instack[v] = 0;
         if(v == s) break;
      }
   }
}

bool ok(int n)
{
    memset(instack ,0 ,sizeof(instack));
    memset(DFN ,0 ,sizeof(DFN));
    memset(LOW ,0 ,sizeof(LOW));
    while(!st.empty()) st.pop();
    Index = 1 ,num = 0;
    for(int i = 0 ;i < n * 2 ;i ++)
   {
    if(DFN[i]) continue;
    Tarjan(i);
   }
   for(int i = 0 ;i < n * 2 ;i += 2)
   if(Belong[i] == Belong[i^1]) return 0;
   return 1;
}
                    
                    
bool solve(int n )
{
    for(int i = 0 ;i < n ;i ++)
    if(B[i][i]) return 0;
    __int64 Key = 1;
    for(int ii = 1 ;ii <= 32 ;ii ++ ,Key *= 2)
    {
       memset(list ,0 ,sizeof(list));
       tot = 1;
       for(int i = 0 ;i < n ;i ++)
       for(int j = 0 ;j < n ;j ++)
       {
          if(i == j) continue;
          int now = B[i][j] & Key;
          if(i % 2 && j % 2)
          {
            if(!now)
            add(i * 2 ,i * 2 + 1) ,add(j * 2 ,j * 2 + 1);
            else add(i * 2 + 1 ,j * 2) ,add(j * 2 + 1 ,i * 2);
          }
          else if(i % 2 == 0 && j % 2 == 0)
          {
              if(!now) 
              add(j * 2 ,i * 2 + 1) ,add(i * 2 ,j * 2 + 1);
              else add(i * 2 + 1 ,i * 2) ,add(j * 2 + 1 ,j * 2);
          }
          else
          {
              if(!now)
              add(i * 2 ,j * 2) ,add(i * 2 + 1 ,j * 2 + 1),
              add(j * 2 ,i * 2) ,add(j * 2 + 1 ,i * 2 + 1);
              else
              add(i * 2 ,j * 2 + 1) ,add(j * 2 ,i * 2 + 1),
              add(i * 2 + 1 ,j * 2) ,add(j * 2 + 1 ,i * 2);
          }
       }
       if(!ok(n)) return 0;
    }
    return 1;
} 

int main ()
{
    int n ,i ,j;
    while(~scanf("%d" ,&n))
    {
       for(i = 0 ;i < n ;i ++)
       for(j = 0 ;j < n ;j ++)
       scanf("%d" ,&B[i][j]);
       solve(n) ? puts("YES") : puts("NO");
    }
    return 0;
}