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 = ; R char c = getchar();
        for(; c < '0' || c > '9'; c = getchar());
        for(; c >='0' && c <='9'; r = r*+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 = ; i <= n+m; i++) f[i] = i; memset(fv, , sizeof(fv));
        for(R int i = ; i <= k; i++)
        {
            x = X[i]; y = Y[i] + n; v = V[i];
            if(x ==  || y == n+) continue;
            fx = find(x);
            fy = find(y);
            R int w = v ^ vis[] ^ (x%==&&y%==?:);
            if(fx != fy)
            {
                f[fx] = fy;
                fv[fx] = w^fv[x]^fv[y];
            }
            else if((fv[x]^fv[y]) != w) return ;
        }
        for(R int i = ; i <= k; i++)
        {
            x = X[i]; y = Y[i] + n; v = V[i];
            if(x ==  || y == n+)
            {
                if(y == n+) y = ;
                x ==  ? x = y : ;
                R int fx = find(x);
                if(vis[fx] != -)
                {
                    if((v ^ vis[fx]) != fv[x]) return ;
                }
                else vis[fx] = v ^ fv[x];
            }
        }
        R int ans = ;
        for(R int i = n+m; i >= ; i--)
        {
            R int fi = find(i);
            if(i == fi && vis[i] == - && i != n+) (ans <<= ) %= MOD;
        }
        return ans;
    }
    void main()
    {
        n = read(), m = read(), k = read();
        for(int i = ; i <= k; i++) X[i] =read(), Y[i] = read(), V[i] = read();
        int ans = ;
        memset(vis, -, sizeof(vis)); vis[] = ; (ans += solve()) %= MOD;
        memset(vis, -, sizeof(vis)); vis[] = ; (ans += solve()) %= MOD;
        printf("%d\n",ans);
    }
}
int main()
{
    runzhe2000::main();
}