轉(zhuǎn)自小yai
把b[][]數(shù)組上的每個(gè)位拆開成兩個(gè)點(diǎn)i和i'，（不超過32位），另外新加兩個(gè)點(diǎn)0和1,如果確定某點(diǎn)i對應(yīng)的是0,則i與0點(diǎn)合并，i'點(diǎn)與1點(diǎn)合并；如果確定某點(diǎn)i對應(yīng)的是1,則i與1合并，i'與0合并；如果確定兩點(diǎn)i和j對應(yīng)的位是相反的數(shù),則i與j'合并，j與i'合并；如果確定兩點(diǎn)對應(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;
}