bzoj 2303 并查集

　　首先如果没有限制的话，我们可以直接求出答案，假设对于n*m的矩阵，我们最上方一行和左方的一列随意确定，那么首先这写确定的状态肯定是不会不合法的，因为我们可以调整剩下的01状态来使得这一行一列的状态合法，而且剩下的01状态唯一确定，我们叫最上面的行和左面的列为标准行列，那么我们对于每一种不同的标准行列都可以有一组合法解，那么最后答案的数量就是标准行列的数量，那么标准行列一共有2^(n+m-1)种方案，那么这就是最后的答案。

　　那么每一个四方阵的1个数为奇数代表这个四方阵的xor和为1，那么根据xor的结合律，我们可以得到一个式子，假设a[i][j]为合法方案中[i][j]位置的数，那么a[1][1]^a[i][j]^a[1][j]^a[i][1]=0或1，当且仅当i,j都为偶数的时候等于0，那么有了这个性质我们可以根据给出的限制判断[1][j]和[i][1]位置的01选择是否相同，那么我们可以将标准行列的每一个点看成两个点，即这个位置选的是0还是1，那么根据给出的限制我们可以知道在这个点选0或1时其余某些点必须选0或1，那么这就是一个简单的2-sat模型了，我们可以连出图之后判断各个连通块中是否有不同的颜色（即题目直接对标准行列做限制），有的话即无解，那么我们可以确定出独立点的个数，即这些点的颜色确定不会对其他点造成影响。

　　对于左上角选1的情况我们只需要把限制中的01状态全部取xor然后再按照上述方法做一遍就可以了。

　　那么在实际操作的时候我们可以用并查集来维护及节点之间的信息，设father[x]为x的父亲节点，ww[x]为x与其父亲节点的关系，ww[x]为0时代表颜色相同，1时则不同，那么我们只需要维护这个就可以了。

　　备注：在合并a,b的时候，设fa为a的父亲应该ww[fa]=ww[a]+ww[b]+a,b节点之间的关系(为01)，结果开始的时候忘了ww[a]了，改了之后又把ww[b]删了，查了半天= =。

/**************************************************************

    Problem: 2303

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:1340 ms

    Memory:71120 kb

****************************************************************/

//By BLADEVIL

#include <cstdio>

#include <cstring>

#define maxn 3000010

#define d39 1000000000

#define LL long long

using namespace std;

struct rec {

    int x,y,z;

}ask[maxn];

int n,m,N,k,w,ans;

int flag[maxn],father[maxn],ww[maxn];

int getfather(int x) {

    if (father[x]==x) return x;

    int fa=father[x];

    father[x]=getfather(fa);

    ww[x]=(ww[x]+ww[fa])%;

    return father[x];

}

int pwr(int x,int k) {

    int ans=;

    while (k) {

        if (k&) ans=(LL)ans*x%d39;

        k>>=;

        x=(LL)x*x%d39;

    }

    return ans;

}

int calc() {

    memset(flag,,sizeof flag);

    memset(ww,,sizeof ww);

    N=n+m-;

    for (int i=;i<=N;i++) father[i]=i;

    for (int i=;i<=k;i++) {

        if (ask[i].x==) {

            int cur;

            if (ask[i].z) cur=; else cur=;

            if (flag[ask[i].y-]) {

                if (flag[ask[i].y-]!=cur) return ; else flag[ask[i].y-]=cur;

            } else flag[ask[i].y-]=cur;

            continue;

        }

        if (ask[i].y==) {

            int cur;

            if (ask[i].z) cur=; else cur=;

            if (flag[ask[i].x+m-]) {

                if (flag[ask[i].x+m-]!=cur) return ; else flag[ask[i].x+m-]=cur;

            } else flag[ask[i].x+m-]=cur;

            continue;

        }

        int a=ask[i].y-,b=ask[i].x+m-;

        //printf("%d %d\n",a,b);

        int fa=getfather(a),fb=getfather(b),add=;

        if ((ask[i].x%==)&&(ask[i].y%==)) {

            if (ask[i].z) add=; else add=;

        } else {

            if (ask[i].z) add=; else add=;

        }

        //printf("%d\n",add);

        if (fa==fb) {

            int cur=(ww[a]+ww[b])%;

            if (cur!=add) return ;

        } else father[fa]=fb; ww[fa]=(ww[b]+ww[a]+add)%;

        //for (int i=1;i<=N;i++) printf("|%d %d %d %d\n",i,father[i],ww[i],flag[i]);

    }

    //for (int i=1;i<=N;i++) printf("|%d %d %d\n",i,father[i],ww[i]);

    //for (int i=1;i<=N;i++) printf("%d ",flag[i]); printf("\n");

    int cnt=;

    for (int i=;i<=N;i++) if (father[i]==i) cnt++;

    //printf("%d ",cnt);

    for (int i=;i<=N;i++) if (flag[i]) {

        if (!flag[getfather(i)]) flag[getfather(i)]=(flag[i]+ww[i])%+; else

        if (flag[getfather(i)]!=(flag[i]+ww[i])%+) return ;

    }

    //for (int i=1;i<=N;i++) printf("%d ",flag[i]); printf("\n");

    for (int i=;i<=N;i++) if ((father[i]==i)&&(flag[i])) cnt--;

    //printf("%d\n",cnt);

    return pwr(,cnt);

}

int main() {

    scanf("%d%d%d",&n,&m,&k);

    for (int i=;i<=k;i++) scanf("%d%d%d",&ask[i].x,&ask[i].y,&ask[i].z);

    for (int i=;i<=k;i++) if ((ask[i].x==)&&(ask[i].y==)) w=i;

    //calc(); return 0;

    if (w) {

        if (ask[w].z)

            for (int i=;i<=k;i++) ask[i].z^=;

        ans=calc();

    } else {

        ans=calc()%d39;

        for (int i=;i<=k;i++) ask[i].z^=;

        (ans+=calc())%=d39;

    }

    printf("%d\n",ans);

    return ;

}

巴特西

bzoj 2303 并查集

最新文章

热门文章