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;
}

hdu4421 2-sat(枚举二进制每一位)

相关推荐