自动搬运

查看原文

来自洛谷，原作者为

	lnwzy VIP=Very Insane Patient

搬运于2025-08-24 22:23:08，当前版本为作者最后更新于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!