#2726. Sam的最短路

#绿，#位运算，#并查集，#化整为零

分析

突破口就在于题目中对于路径长度的定义：路径上所有边权的按位和。

对于一条路径，判断非常复杂，考虑化整为零。
化整为零：将边权的按位和与 $V$ 作比较 $\rightarrow$ 每一个边权与 $V$ 作比较。

高位联通

“高位”是指高于 $V$ 最高位的位置。
高位联通的情况相对简单，一条路径上的边在同一个高位是 1，那么就可以连通。

V  = 01010
w1 = 10000
w2 = 10010

单独判断
w1 & V = 0
w2 & V = 10

按位与，再判断
w1 & w2 = 10000

对于每一个高位（$V$ 没有达到的位），维护一个并查集，合并的条件是 $w \& 2^k = 2^k$。

查询时枚举所有高位，判断两点是否在同一集合内。

低位联通

“低位”是指不高于 $V$ 最高位的位置。
低位联通相对复杂一些。

设 $V$ 的最高位为 $h_{max}$。
令 $x(h)$ 代表：$x$ 二进制第 $h$ 位上的数。

• 从 $h_{max}$ 开始枚举数位。同时维护一个边集 $S = E$。
• 设当前是第 $h$ 位。枚举 $S$ 中的边 $(u,v,w)$。
• 如果 $V(h) = 0$。
  • 如果 $w(h) = 0$，那么这条边可能存在于长度等于 $V$ 的路径。因此不可以将它踢出边集。
  • 如果 $w(h) = 1$，那么这条边一定存在于长度大于 $V$ 的路径。因此用它更新第 $h$ 层的并查集。
• 如果 $V(h) = 1$。
  • 如果 $w(h) = 0$，那么这条边不可能存在于长度等于 $V$ 的路径。将这条边从 $S$ 中踢出。
  • 如果 $w(h) = 1$，那么这条边可能存在于长度等于 $V$ 的路径。因此不可以将它踢出边集。

上面这个分类讨论很像数位 dp 中的二叉分类树。因此，“右下角的叶子节点”我们也不能忽略。

• 当上述流程结束后，边集 $S$ 中依然存在一些边，这些边一定存在于长度为 $V$ 的路径，开一个新的并查集维护。

反思与理解要点

说实话，我觉得这一题并不是非常好想。这可能是我长期不接触甚至逃避位运算问题导致的。

不太好理解的部分是低位联通。有一些要点需要重点考察与关注。

• “一定”“可能”“不可能”等可能性表述。
• 第 $h$ 层并查集的含义。
  • 定义一个边集。这个边集中的边的边权，在 $\forall i \in [h_{maxh},h-1], w(i) \ge V(i)$。特别地，$w(h) \gt V(i)$。
  • 第 $h$ 层的并查集，是由上述边集所造成的联通关系。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 5e5 + 10;

struct Line{
	int u, v;
	LL w;
}line[M];

int n, m, T, maxh, fa[N][65], vis[M];
LL V;

int getfa(int x, int h){
	if(fa[x][h] == x) return x;
	else return fa[x][h] = getfa(fa[x][h], h);
}

void merge(int x, int y, int h){
	if(getfa(x, h) != getfa(y, h)) fa[getfa(x, h)][h] = getfa(y, h);
}

int main(){
	freopen("dis.in", "r", stdin);
	freopen("dis.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> m >> V;
	for(int i = 1; i <= m; i ++){
		int u, v; LL w;
		cin >> u >> v >> w;
		line[i] = {u, v, w};
	}
	
	//求 V 的二进制最高位
	maxh = 0;
	for(int i = 59; i >= 0; i --){
		if(V>>i & 1){
			maxh = i;
			break;
		}
	}
	
	//init of dsu
	for(int h = 0; h <= 60; h ++){
		for(int i = 1; i <= n; i ++){
			fa[i][h] = i;
		}
	}
	
	//高位联通
	for(int h = 59; h > maxh; h --){
		for(int i = 1; i <= m; i ++){
			int u = line[i].u, v = line[i].v; LL w = line[i].w;
			if(w>>h &1) merge(u, v, h);
		}
	}
	
	//低位联通, vis[i] = 0代表这条边还在边集中
	for(int h = maxh; h >= 0; h --){
		if(V>>h & 1){
			//如果w(h)==0,则踢出边集
			for(int i = 1; i <= m; i ++){
				if(vis[i]) continue;
				LL w = line[i].w;
				if(!(w>>h & 1)) vis[i] = 1;
			}
		}else{//V(h) == 0
			//如果w(h)==1, 则维护一个并查集
			for(int i = 1; i <= m; i ++){
				if(vis[i]) continue;
				int u = line[i].u, v = line[i].v; LL w = line[i].w;
				if(w>>h&1) merge(u, v, h);
			}
		}
	}
	//剩余边也要连起来，存储在h = 60
	for(int i = 1; i <= m; i ++){
		if(vis[i]) continue;
		int u = line[i].u, v = line[i].v;
		merge(u, v, 60);		
	}
	
	
	//查询
	cin >> T;
	while(T--){
		int u, v;
		cin >> u >> v;
		bool flag = 0;
		for(int h = 0; h <= 60; h ++){
			if(getfa(u, h) == getfa(v, h)){
				flag = 1;
				break;
			}
		}
		if(flag) cout << "Yes\n";
		else cout << "No\n";
	}
	
	return 0;
}