BZOJ 2303 [Apio2011]方格染色

易或方程+带权并查集

我好SB啊，挂题解吧。。。。。。 http://www.cnblogs.com/HHshy/p/5840018.html

#include<cstdio> #include<cstring> #define N 2333333 #define MOD 1000000000 #define R register using namespace std; namespace runzhe2000 { int read() { R int r = 0; R char c = getchar(); for(; c < '0' || c > '9'; c = getchar()); for(; c >='0' && c <='9'; r = r*10+c-'0', c = getchar()); return r; } int n, m, k, f[N], fv[N], vis[N], X[N], Y[N], V[N]; int find(R int x) { if(f[x] == x) return x; else { R int y = find(f[x]); fv[x] ^= fv[f[x]]; return f[x] = y; } } int solve() { R int x, y, v, fx, fy; for(R int i = 1; i <= n+m; i++) f[i] = i; memset(fv, 0, sizeof(fv)); for(R int i = 1; i <= k; i++) { x = X[i]; y = Y[i] + n; v = V[i]; if(x == 1 || y == n+1) continue; fx = find(x); fy = find(y); R int w = v ^ vis[1] ^ (x%2==0&&y%2==0?1:0); if(fx != fy) { f[fx] = fy; fv[fx] = w^fv[x]^fv[y]; } else if((fv[x]^fv[y]) != w) return 0; } for(R int i = 1; i <= k; i++) { x = X[i]; y = Y[i] + n; v = V[i]; if(x == 1 || y == n+1) { if(y == n+1) y = 1; x == 1 ? x = y : 0; R int fx = find(x); if(vis[fx] != -1) { if((v ^ vis[fx]) != fv[x]) return 0; } else vis[fx] = v ^ fv[x]; } } R int ans = 1; for(R int i = n+m; i >= 1; i--) { R int fi = find(i); if(i == fi && vis[i] == -1 && i != n+1) (ans <<= 1) %= MOD; } return ans; } void main() { n = read(), m = read(), k = read(); for(int i = 1; i <= k; i++) X[i] =read(), Y[i] = read(), V[i] = read(); int ans = 0; memset(vis, -1, sizeof(vis)); vis[1] = 0; (ans += solve()) %= MOD; memset(vis, -1, sizeof(vis)); vis[1] = 1; (ans += solve()) %= MOD; PRintf("%d\n",ans); } } int main() { runzhe2000::main(); }