自动搬运

查看原文

来自洛谷，原作者为

	FFFFFAN 做人类很难，但是我们选择去月球。 // AFAFO，复活！

搬运于2025-08-24 22:49:38，当前版本为作者最后更新于2023-11-09 13:32:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

RT，本题还真不是一道路径查询题，这里提供一个并查集做法。

题意

给定一个无向图和一个常数 $V$，有多次询问，每次询问两个点之间是否存在一条路径，使得路径上所有边的边权进行按位与计算的结果不小于 $V$。

思路

首先来思考一下按位与运算的性质。发现，两个数相与的结果一定不大于这两个数，因为按位与运算只有可能把二进制位上的 $1$ 变成 $0$，而 $0$ 不可能会变成 $1$，所以一直做按位与运算只会越来越小。

这引导我们从二进制上分析，假设从高位往低位分析，那么两个数按位与后不小于另一个数，必须存在 $i$，使得高于 $i$ 的所有位中，要么三个数同为 $1$，要么另一个数这一位为 $0$ 而这两个数的这一位可为 $1$ 也可为 $0$，也是按位与的结果的一段前缀要不小于另一个数的相同位置的一段前缀。

推广到更多数的情况，那么一些边的边权按位与的结果要不小于 $V$，也就是这些边的边权都存在一个前缀满足上面的条件，那么这些边权按位与的结果就一定会满足上面的条件。

$V,w_i\lt 2^{60}$，即前缀只有 $60$ 个，我们考虑按每一条边的边权前缀将这些边分类，满足第 $i$ 个边集里面的所有边的边权的按位与的前 $i$ 位这个前缀大于 $V$ 的前 $i$ 位的前缀。

这样，如果 $u$ 到 $v$ 存在一条路径满足路径上的所有边都在同一个集合里面，那么这条路径上所有边的边权的按位与就会不小于 $V$，相当于判断 $u$ 和 $v$ 是否在某个全部由同一边集的边形成的子图中是联通的，而这用并查集可以很好的维护。

当然，某一条边的边权如果有多个前缀满足条件，那这条边会同时存在于多个边集中。并且我们要特殊处理一下边权等于 $V$ 的所有边，由这些边形成的子图中的任意两点也是满足题意的。

建边的时间复杂度 $O(m)$，一次查询的时间复杂度就是并查集的时间复杂度。

代码

#include<cstdio>
using namespace std;

int n, m, q, fa[100005][65], b[65];
long long V;

int find(int x, int i) {
	return x==fa[x][i] ? x : fa[x][i]=find(fa[x][i], i);
}

int main() {
	scanf("%d%d%d%lld", &n, &m, &q, &V);
	for(int i=1; i<=n; ++i)
		for(int j=0; j<=61; ++j)	fa[i][j] = i;
	for(int j=60; ~j; --j)
		if(V&(1ll<<j))	b[j] = 1;
	for(int i=1; i<=m; ++i) {
		int u, v;
		long long w;
		scanf("%d%d%lld", &u, &v, &w);
		for(int j=60; ~j; --j) {
			bool f = (w&(1ll<<j));
			if((!b[j]) && f)	fa[find(u, j)][j] = find(v, j);
			else if(b[j] && (!f))	break;
		}
		if((w&V) >= V)	fa[find(u, 61)][61]=find(v, 61);
	}
	for(int i=1; i<=q; ++i) {
		int u, v, flag=0;
		scanf("%d%d", &u, &v);
		for(int j=61; ~j; --j)
			if(find(u, j) == find(v, j)) {
				flag = 1;
				break;
			}
		puts(flag ? "Yes" : "No");
	}
	return 0;
}

附录

原题链接

[SDCPC2023] Not Another Path Query Problem - 洛谷

参考文献

扶苏姐姐的课