【2024秋令营 #18 A】图论题（并查集 + 位运算 trick）

$\large{\cal{ZhangWenjie}}$ / 2024-10-15 / 原文

一开始的做法是，我就简单地以为是最短路的变式，只不过是累加变成累按位或

然后。。。就喜提 55pts

感觉很假，也不多说什么了

code

#include <bits/stdc++.h>
#define re register int 

using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 1e5 + 10, M = 1e6 + 10;
const LL inf = LLONG_MAX;

struct Edge
{
	int to, next;
	LL w;
}e[M];
int top, h[N];
LL dist[N];
int n, m;
bool st[N];

inline void add(int x, int y, LL w)
{
	top ++;
	e[top].to = y, e[top].w = w, e[top].next = h[x];
	h[x] = top;
}

inline void dijkstra()
{
	priority_queue<PII, vector<PII>, greater<PII> > q;
	for (re i = 1; i <= n; i ++) dist[i] = inf; 
	dist[1] = 0ll;
	q.push({dist[1], 1});
	
	while (!q.empty())
	{
		int x = q.top().second; q.pop();
		if (st[x]) continue;
		st[x] = true;
		
		for (re i = h[x]; i; i = e[i].next)
		{
			int y = e[i].to; LL w = e[i].w;
			if (dist[y] > (dist[x] | w))
			{		
				dist[y] = (dist[x] | w);
				q.push({dist[y], y});
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	while (m --)
	{
		LL x, y, z; cin >> x >> y >> z;
		if (x == y) continue;
		add(x, y, z);
		add(y, x, z);
	}
	dijkstra();
	cout << dist[n] << '\n';
	
	return 0;
}

观察到是按位或操作，位运算，那么多半跟二进制会扯上关系

考虑从二进制角度思考

发现题目给定 $w_i< 2^{63}$，我们知道按位或的结果是单调不降的，也就是说，越或越大，但不会超过 $2^{63} - 1$

最终的答案肯定是这些 01 串组成的二进制数，再转十进制输出

那么如果考虑枚举这 62 位，要么是 0，要么是 1，发现很可做

显然，对于第 i 位，我们总是希望填 0，

具体地，一开始初始化结果全为 1，即 1111......111

从高位开始确定，到第 i 位，我们希望这一位变成 0，即 xxxx(i->)0 ... 111

那么我们可以跑一遍图，将与该状态下按位或不冲突的边标记，如果能形成 1 -> n 的通路，说明在第 i 位上填 0 合法

否则则必须填 1（因为联通图，所以此时必有通路）

那么可以用 并查集 维护，也可以 dfs 当然

时间复杂度 $O(m\log n\log W)$

#include <bits/stdc++.h>
#define re register int 

using namespace std;
typedef long long LL;
const int N = 5e5 + 10;

int n, m, u[N], v[N], fa[N];
LL w[N];

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (re i = 1; i <= m; i ++) cin >> u[i] >> v[i] >> w[i];
	
	LL ans = (1ll << 63) - 1; // 我这个 ll 怎么显示得跟 1 似的
	for (LL k = 62; k >= 0; k --)
	{
		for (re i = 1; i <= n; i ++) fa[i] = i;
		ans ^= (1ll << k);
		
		for (re i = 1; i <= m; i ++)
			if ((ans | w[i]) == ans)
			{
				int x = u[i], y = v[i];
				if (find(x) != find(y))
				{
					fa[find(x)] = find(y);
				}
			}
		if (find(1) != find(n)) ans |= (1ll << k);
	}
	cout << ans << '\n';
	
	return 0;
}

练习：

P9565 [SDCPC2023] Not Another Path Query Problem