轉自小yai
把b[][]數組上的每個位拆開成兩個點i和i'，（不超過32位），另外新加兩個點0和1,如果確定某點i對應的是0,則i與0點合并，i'點與1點合并；如果確定某點i對應的是1,則i與1合并，i'與0合并；如果確定兩點i和j對應的位是相反的數,則i與j'合并，j與i'合并；如果確定兩點對應的位是相同的數，則i與j合并，i'與j'合并。
最近比較忙，所以題解比較水，所以具體還是看代碼吧。
因為要空出數給0點和1點，所以我從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;
}