题解 P6691 【选择题】

lnwzy · 2021-02-02 21:50:57 · 题解

为什么很多人都用DFS或BFS啊？这题不是经典的带权并查集吗？

这道题和关押罪犯可以说几乎一样了。当opt为1时，说明两个选项要么一起对，要么一起错，连一条权为0的边，当opt为0时，说明两个选项一个对，一个错，连一条权为1的边。于是我们要开一个r数组，表示与父节点的关系。

那么很简单的问题来了：当父节点发生变化时如何更新r数组？

解决方法是：在路径压缩时多加一步。

像这样：

int fa(int x)
{
    if(f[x]==x)
    {
        return f[x];
    }
    int t=f[x];
    f[x]=fa(f[x]);
    r[x]=(r[t]+r[x])%2;//就是这一步
    return f[x];
}

为什么自己想去。

接下来我再给大家演示一下如何合并并查集：

int tmp=fa(i);
f[fa(i)]=fa(a);
r[tmp]=(r[i]+opt+1+r[a])%2;

求答案数的过程是个简单的排列组合，每一个并查集都有两种情况：根节点正确或根节点错误，所以只需要求并查集数量就行了，数量是2的并查集数量次方。我们还需要开一个num数组，记录与根节点相同的选项数量和与根节点矛盾的选项数量。这样在求最多正确答案时把较多的加上去，在求最少正确答案时把较小的加上去。没说明白的话我会在代码里解释清楚。

上代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int f[1000005],r[1000005],num[1000005][5];
int fa(int x)
{
    if(f[x]==x)
    {
        return f[x];
    }
    int t=f[x];
    f[x]=fa(f[x]);
    r[x]=(r[t]+r[x])%2;
    return f[x];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int a,opt;
        scanf("%d%d",&a,&opt);
        if(fa(i)!=fa(a))
        {
            int tmp=fa(i);
            f[fa(i)]=fa(a);
            r[tmp]=(r[i]+opt+1+r[a])%2;
        }else
        {
            if((r[i]+r[a])%2!=(opt+1)%2)
            {
                printf("No answer");//判断无解
                return 0;
            }
        }   
    }
    for(int i=1;i<=n;i++)
    {
        if(fa(i)==i)
        {
            num[i][0]++;
        }else
        {
            num[fa(i)][r[i]]++;
        }
    }
    int maxans=0,minans=0,tot=1;
    for(int i=1;i<=n;i++)
    {
        if(fa(i)==i)
        {
            tot=tot*2%998244353;//答案数
            maxans+=max(num[i][1],num[i][0]);//累加较大的正确答案
            minans+=min(num[i][1],num[i][0]);//累加较小的正确答案    
        }   
    }
    printf("%d\n%d\n%d\n",tot,maxans,minans);
    return 0;
}

Thanks for your attention!