轉(zhuǎn)自小yai
把b[][]數(shù)組上的每個(gè)位拆開成兩個(gè)點(diǎn)i和i'，（不超過(guò)32位），另外新加兩個(gè)點(diǎn)0和1,如果確定某點(diǎn)i對(duì)應(yīng)的是0,則i與0點(diǎn)合并，i'點(diǎn)與1點(diǎn)合并；如果確定某點(diǎn)i對(duì)應(yīng)的是1,則i與1合并，i'與0合并；如果確定兩點(diǎn)i和j對(duì)應(yīng)的位是相反的數(shù),則i與j'合并，j與i'合并；如果確定兩點(diǎn)對(duì)應(yīng)的位是相同的數(shù)，則i與j合并，i'與j'合并。
最近比較忙，所以題解比較水，所以具體還是看代碼吧。
因?yàn)橐粘鰯?shù)給0點(diǎn)和1點(diǎn)，所以我從1到n而不是從0到n-1,所以奇偶性的判斷要換一下。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000;
int p[maxn];
int b[505][505];
int n;
void init() {
    for(int i=0;i<(2*n+1)*32+100;i++) p[i] = i;   
}
int find(int x) {
    return x==p[x] ? x : p[x] = find(p[x]);   
}
void Union(int x,int y) {
    int a = find(x) , b = find(y);
    p[a] = p[b] = p[x] = p[y] = min(a , b);   
}
bool check() {
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++)
            if(b[i][j] != b[j][i]) return 0;
        if(b[i][i] != 0) return 0;   
    }
    init();
    int m = 32 * n;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++) {
            if(i % 2 == 0 && j % 2 == 0) {
                for(int k=0;k<32;k++) {
                    if(b[i][j] & (1<<k) == 0) {
                        int u = i*32+k , v = j*32+k;
                        if(find(u) == find(1) || find(v) == find(1) || find(u) == find(v+m)) return 0;
                        Union(u,0);
                        Union(v,0);
                        Union(u+m,1);
                        Union(v+m,1);
                    }   
                }   
            }   
            else if(i % 2 == 1 && j % 2 == 1) {
                for(int k=0;k<32;k++) {
                    if(b[i][j] & (1<<k)) {
                        int u = i* 32 + k , v = j*32+k;
                        if(find(u) == find(0) || find(v)==find(0) || find(u) == find(v+m)) return 0;
                        Union(u,1);
                        Union(v,1);
                        Union(u+m,0);
                        Union(v+m,0);   
                    }   
                }   
            }
            else {
                for(int k=0;k<32;k++) {
                    int u = i * 32 + k , v = j * 32 + k;
                    if(b[i][j] & (1<<k)) {
                        if(find(u) == find(v)) return 0;
                        Union(u,v+m);
                        Union(u+m,v);   
                    }
                    else {
                        if(find(u) == find(v+m)) return 0;
                        Union(u,v);
                        Union(u+m,v+m);   
                    }
                }   
            }
        }
    return 1;
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&b[i][j]);
        if(check()) puts("YES");
        else puts("NO");   
    }
    return 0;   
}