BZOJ2303: [Apio2011]方格染色 并查集

bzoj2303.cpp

#include <cstdio>
#include <cstring>
const int N = 1000000 + 9,MOD = 1000000000;
int f[N],son[N],lnk[N],nxt[N],v[N],fa[N],pre[N],n,wei[N],ec,m,k;
int tmp[100][100];
bool mark[N];
int getf(int x){return x == f[x] ? x : f[x] = getf(f[x]);}
inline void addedge(int x,int y,int z)
{
    nxt[++ec] = son[x];
    son[x] = ec;
    lnk[ec] = y;
    wei[ec] = z;
}
int getf1(int x)
{
    if (x == fa[x]) return x;
    int father = getf1(fa[x]);
    pre[x] ^= pre[fa[x]];
    return fa[x] = father;
}
bool add(int x,int y,int z)
{
    int fx = getf1(x),fy = getf1(y);
    if (fx != fy) {
        fa[fx] = fy;
        pre[fx] = pre[x] ^ pre[y] ^ z;
        return true;
    }else return !(pre[x] ^ pre[y] ^ z);
}
int calc()
{
    memset(v,-1,sizeof v);
    for (int i = 1; i <= m; ++i) fa[i] = i,pre[i] = 0;
    for (int i = son[1],p = -1,val; i; i = nxt[i]) {
        v[lnk[i]] = wei[i];
        if (p != -1 && !add(lnk[i],p,(val ^ wei[i])))
            return 0;
        p = lnk[i];
        val = wei[i];
    }
    for (int i = 1; i <= n; ++i) {
        int father = -1;
        for (int j = son[i]; j; j = nxt[j])
            if (father == -1) father = lnk[j];
            else {
                int fx = getf(father),fy = getf(lnk[j]);
                if (fx != fy) {
                    if (v[fx] != -1) f[fy] = fx;
                    else f[fx] = fy;
                }
            }
    }
    int ans = 1;
    for (int i = 1; i <= m; ++i) if (v[getf(i)] == -1) v[getf(i)] = 0,(ans *= 2) %= MOD;
    for (int i = 2; i <= n; ++i) {
        int p[2] = {-1,-1},val[2];
        for (int j = son[i]; j; j = nxt[j]) {
            if (p[lnk[j]&1] != -1)
                if (!add(p[lnk[j]&1],lnk[j],(val[lnk[j]&1] ^ wei[j])))
                    return 0;
            val[lnk[j]&1] = wei[j];
            p[lnk[j]&1] = lnk[j];
        }
        if (i == 2)
            i = 2;
        if (p[0] != -1 && p[1] != -1)
            if (!add(p[0],p[1],(((i - 1) & 1) ^ val[0] ^ val[1])))
                return 0;
    }
    for (int i = 1; i <= m; ++i)
        if (v[getf1(i)] == -1) v[getf1(i)] = 0;
    // for (int i = 1; i <= m; ++i) {
    //  getf1(i);
    //  printf("%d",pre[i]^v[getf1(i)]);
    // }puts("");
    for (int i = 2; i <= n; ++i)
        if (!son[i]) (ans *= 2) %= MOD;
    return ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("2303.in","r",stdin);
    freopen("2303.out","w",stdout);
    #endif
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1; i <= m; ++i) f[i] = i;
    // for (int i = 1; i <= n; ++i)
    //  for (int j = 1; j <= m; ++j) tmp[i][j] = 2;
    for (int i = 1,x,y,z; i <= k; ++i) {
        scanf("%d%d%d",&x,&y,&z);
        //tmp[x][y] = z;
        addedge(x,y,z);
    }
    // for (int i = 1; i <= n; ++i) {
    //  for (int j = 1; j <= m; ++j)
    //      if (tmp[i][j] == 2) putchar('_');
    //      else printf("%d",tmp[i][j]);
    //  puts("");
    // }
    printf("%d\n",calc());
}