[2-sat][位运算]zoj 3656：Bit Magic

大致题意：
    给出下面一段代码

    很明显这段代码是用a[n]数组来计算出b[n][n]。

void calculate(int a[N], int b[N][N]) {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i == j) b[i][j] = 0;
			else if (i % 2 == 1 && j % 2 == 1) b[i][j] = a[i] | a[j];
			else if (i % 2 == 0 && j % 2 == 0) b[i][j] = a[i] & a[j];
			else b[i][j] = a[i] ^ a[j];
		}
	}
}

 现在给出b[n][n]数组，求是否存在一个合法的a[n]数组，使其能计算出已经给出的b[][];

 

大致思路：

    2-sat的思路很容易想到，就是考虑所有数字的31个位，对所有的位分为两组-----这个位是0，这个位是1，再按照上面的代码建立逻辑关系，再建图2-sat。

 

#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=6000;
const int mMax=1000010;
class edge{
public:
    int v,nex;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部

void addedge(int a,int b){//向图中加边的算法，注意加上的是有向边//b为a的后续节点既是a---->b
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}

int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep;   //atype 强连通分量的个数
bool insta[nMax];

void Tarjan(int u){                 //我的Tarjan模版
    int i,j;
    dfn[u]=low[u]=++dep;
    sta[++top]=u;
    insta[u]=1;
    for(i=head[u];i;i=e[i].nex){
        int v=e[i].v;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(insta[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        atype++;              //强连通分量个数
        do{
            j=sta[top--];
            belon[j]=atype;   //第j个点属于第type个连通块
            insta[j]=0;
        }while(u!=j);
    }
}

void init(){
    k=1;
    dep=1;
    top=atype=0;
    memset(insta,0,sizeof(insta)); //是否在栈中
    memset(head,0,sizeof(head));   //静态链表头指针
    memset(low,0,sizeof(low));     //Tarjan的low数组
    memset(dfn,0,sizeof(dfn));     //Tarjan的dfn数组
    memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
}

int n,m;
int mtx[600][600];
bool judge(){
    for(int i=0;i<n;i++){
        if(belon[i]==belon[i+n]){
            return 0;
        }
    }
    return 1;
}
int main(){
    int i,j,m,a1,a2,num;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&mtx[i][j]);
            }
        }
        bool flag=1;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(mtx[i][j]!=mtx[j][i])
                {
                    flag=0;
                    break;
                }
                if(i==j&&mtx[i][j]!=0)
                {
                    flag=0;
                    break;
                }
            }
        }
        if(!flag)
        {
            cout<<"NO\n";
            continue;
        }
        flag=1;
        int left;
        for(left=0;left<31;left++)
        {
            num=n;
            init();
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    m=mtx[i][j]&(1<<left);
                    if(i==j)continue;
                    else if (i % 2 == 1 && j % 2 == 1)   //// |
                    {
                        a1=i;
                        a2=j;
                        if(m!=0)
                        {
                            addedge(a1+num,a2);
                            addedge(a2+num,a1);
                        }
                        else
                        {
                            addedge(a1,a1+num);
                            addedge(a2,a2+num);
                        }
                    }
                    else if (i % 2 == 0 && j % 2 == 0)    //////&
                    {
                        a1=i;
                        a2=j;
                        if(m!=0)
                        {
                            addedge(a1+num,a1);
                            addedge(a2+num,a2);
                        }
                        else
                        {
                            addedge(a1,a2+num);
                            addedge(a2,a1+num);
                        }
                    }
                    else                                 /////   ^
                    {
                        a1=i;
                        a2=j;
                        if(m!=0)
                        {
                            addedge(a1,a2+num);
                            addedge(a2,a1+num);
                            addedge(a1+num,a2);
                            addedge(a2+num,a1);
                        }
                        else
                        {
                            addedge(a1,a2);
                            addedge(a2,a1);
                            addedge(a1+num,a2+num);
                            addedge(a2+num,a1+num);
                        }
                    }
                }
            }

            for(i=0;i<num*2;i++)
            {
                if(!dfn[i])Tarjan(i);
            }
            n=num;
            if(!judge())
            {
                flag=0;
                break;
            }
        }

        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}