旅途的最小代价补写
2026-07-22 20:53:05
发布于：广东
带权无向图中按位与旅途的最小代价
一、题目要求
给定一个带权无向图。
一趟旅途可以：
- 重复经过同一个节点；
- 重复经过同一条边；
- 绕路之后再回到原来的位置。
一趟旅途的代价，是经过的所有边权的按位与：
w1 & w2 & w3 & ...
对于每个询问 s t，要求从 s 到 t 的所有旅途中，代价最小是多少。
如果 s 和 t 不连通，输出 -1。
二、你的代码原本想做什么
你的思路是：
- 从起点
s开始 DFS； - 每走过一条边，就把当前答案和边权进行按位与；
- 到达终点
t时，更新最小答案。
也就是：
void dfs(int p, int t, int r = -1){
if(p == t){
ans = min(ans, r);
return;
}
for(const node& e : mp[p]){
int newR = e.w;
if(r != -1){
newR &= r;
}
dfs(e.id, t, newR);
}
}
这个思路的问题在于：题目允许重复经过节点和边，所以可能存在无限多趟旅途。
三、原代码存在的问题
1. 没有使用 vis，会无限递归
这是无向图。
假设存在一条边：
0 —— 1
从 0 走到 1 后，DFS 又可以从 1 走回 0：
0 → 1 → 0 → 1 → 0 → ...
因此程序会无限递归，最终栈溢出。
虽然你定义了：
bool vis[114514];
但是在 DFS 中并没有使用它。
2. 不能简单地用 vis 禁止重复访问
可能会想到这样修改：
vis[p] = true;
for(const node& e : mp[p]){
if(!vis[e.id]){
dfs(e.id, t, ...);
}
}
但这样也不正确。
因为题目明确允许重复经过节点和边，而且最优旅途可能必须绕路。
例如样例一：
0 --7-- 1 --7-- 3
|
1
|
2
从 0 到 3 的简单路径是：
0 → 1 → 3
代价为：
7 & 7 = 7
但是我们可以绕路：
0 → 1 → 2 → 1 → 3
代价为：
7 & 1 & 1 & 7 = 1
所以如果禁止重复访问节点，就可能找不到最优答案。
3. 第一次到达终点时不能直接停止
你的代码中：
if(p == t){
ans = min(ans, r);
return;
}
但第一次到达 t 后，还可以离开 t，经过一些权值更小的边，再回到 t。
例如：
s --7-- t --1-- x
从 s 直接到 t，代价是：
7
但是可以走：
s → t → x → t
代价为：
7 & 1 & 1 = 1
因此到达终点不代表旅途必须立刻结束。
4. 每个询问都 DFS，时间复杂度无法接受
数据范围为：
n,m,q ≤ 10^5
如果每个询问都遍历整张图，时间复杂度大约是：
O(q(n+m))
最坏情况下接近：
10^5 × 10^5 = 10^10
一定会超时。
四、按位与运算的特点
按位与有一个重要性质：
参与按位与的数字越多，结果只可能不变或者变小，不可能变大。
例如：
15 = 1111
15 & 7 = 0111
7
7 & 6 = 0110
6
6 & 1 = 0000
0
每多经过一条边，代价中的某些二进制位可能从 1 变成 0。
一旦某一位变成了 0，以后不可能重新变成 1。
五、关键结论
对于同一个连通块中的任意两个节点 s 和 t：
从
s到t的最小旅途代价，等于这个连通块中所有边权的按位与结果。
假设一个连通块中的所有边权为：
w1,w2,w3,...,wk
那么这个连通块中任意两个节点之间的答案都是：
w1 & w2 & w3 & ... & wk
如果两个节点不在同一个连通块中，答案就是 -1。
六、为什么答案是整个连通块的边权按位与
可以从二进制的每一位分别考虑。
假设我们正在研究二进制的第 k 位。
情况一：连通块中所有边的第 k 位都是 1
无论选择怎样的旅途，经过的每条边在这一位都是 1。
所以最终按位与结果的第 k 位一定是 1。
情况二：连通块中至少有一条边的第 k 位是 0
由于整个连通块是连通的，我们可以从 s 出发，绕路经过这条边，然后再走到 t。
一旦经过了这条第 k 位为 0 的边，最终答案的第 k 位就会变成 0。
因此，只要连通块中存在一条边的某一位是 0，我们就能让答案的这一位变成 0。
所以最终：
- 某一位在所有边中都是
1，答案中这一位才是1； - 某一位只要在某条边中是
0，答案中这一位就可以是0。
这正是对整个连通块的所有边权进行按位与。
七、为什么一定可以经过连通块中的所有边
因为题目满足两个重要条件：
- 图是无向图；
- 旅途允许重复经过节点和边。
假设我们现在位于某个节点，想去经过连通块中的某条边。
由于连通块内部任意两个节点之间都存在路径，所以我们一定可以：
- 从当前位置走到这条边的一个端点；
- 经过这条边；
- 再继续走向其他边；
- 最后走到终点
t。
中间即使重复经过其他节点或边也没有关系。
因此，我们能够构造一趟旅途，使它经过连通块中的所有边。
八、DFS 应该怎样使用
原本你的 DFS 是：
对每个询问，搜索从
s到t的所有旅途。
这个做法无法实现。
我们把它改成：
对整张图进行 DFS，找出每个连通块，并计算每个连通块中所有边权的按位与。
需要记录两个信息：
belong[i]
表示节点 i 属于哪个连通块。
cost[id]
表示编号为 id 的连通块中，所有边权的按位与。
九、DFS 的实现
void dfs(int p, int id){
vis[p] = true;
belong[p] = id;
for(const node& e : mp[p]){
cost[id] &= e.w;
if(!vis[e.id]){
dfs(e.id, id);
}
}
}
这里有一个非常重要的细节：
cost[id] &= e.w;
必须放在：
if(!vis[e.id])
的外面。
也就是不能写成：
if(!vis[e.id]){
cost[id] &= e.w;
dfs(e.id, id);
}
因为这样只会计算 DFS 树上的边，而不会计算连通块中形成环的其他边。
例如：
0 --7-- 1
\ /
3 6
\ /
2
DFS 可能只通过两条边访问所有节点，但第三条边同样属于这个连通块，也必须参与按位与。
十、为什么同一条无向边计算两次没有问题
建立无向图时，一条边会存储两次：
mp[u].push_back({v, w});
mp[v].push_back({u, w});
因此 DFS 会对同一个权值计算两次：
x & w & w
但按位与满足：
w & w = w
所以：
x & w & w = x & w
重复计算不会影响答案，不需要专门判断每条边是否已经处理。
十一、初始值为什么使用 -1
每个连通块开始时，可以令：
cost[id] = -1;
在二进制补码中，-1 的所有二进制位都是 1：
11111111111111111111111111111111
所以：
-1 & w = w
例如：
-1 & 7 = 7
这样第一次遇到边权时，cost[id] 就会变成这条边的权值。
之后再继续与其他边权：
cost[id] &= e.w;
十二、询问的处理
对于一个询问：
s t
先判断：
belong[s] == belong[t]
不在同一个连通块
说明不存在从 s 到 t 的旅途：
cout << -1;
在同一个连通块
答案就是：
cost[belong[s]]
每个询问只需要常数时间。
十三、完整代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
struct node{
int id;
int w;
};
vector<node> mp[N];
int n, m;
// vis[i]：节点 i 是否已经在预处理中被访问
bool vis[N];
// belong[i]：节点 i 所属的连通块编号
int belong[N];
// cost[id]：第 id 个连通块中所有边权的按位与
int cost[N];
void dfs(int p, int id){
vis[p] = true;
belong[p] = id;
for(const node& e : mp[p]){
// 连通块中的每一条边都要参与按位与
cost[id] &= e.w;
if(!vis[e.id]){
dfs(e.id, id);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> m;
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
mp[u].push_back({v, w});
mp[v].push_back({u, w});
}
int cnt = 0;
// 预处理所有连通块
for(int i = 0; i < n; i++){
if(!vis[i]){
cnt++;
cost[cnt] = -1;
dfs(i, cnt);
}
}
int q;
cin >> q;
while(q--){
int s, t;
cin >> s >> t;
// 不在同一个连通块，无法到达
if(belong[s] != belong[t]){
cout << -1 << '\n';
}
// cost 为 -1，说明这是一个没有任何边的孤立点
else if(cost[belong[s]] == -1){
cout << -1 << '\n';
}
else{
cout << cost[belong[s]] << '\n';
}
}
return 0;
}
十四、样例一分析
边为：
0 --7-- 1
|
1
|
2
1 --7-- 3
节点 0、1、2、3 属于同一个连通块。
这个连通块中所有边权的按位与为：
7 & 7 & 1 = 1
因此，只要询问的两个节点都在这个连通块中，答案就是 1。
对于询问：
0 3
答案为：
1
节点 4 是孤立点，所以询问：
3 4
两个节点不连通，答案为：
-1
十五、样例二分析
所有边权为：
15、7、6、1
进行按位与：
15 & 7 & 6 & 1
写成二进制：
15 = 1111
7 = 0111
6 = 0110
1 = 0001
所以：
1111
0111
0110
0001
----
0000
最终结果为：
0
因此询问 1 2 的答案是 0。
十六、复杂度分析
预处理
DFS 会访问每个节点一次，每条无向边会被处理两次：
O(n+m)
回答询问
每个询问只需要判断两个节点的连通块编号：
O(1)
一共有 q 个询问：
O(q)
总时间复杂度
O(n+m+q)
空间复杂度
邻接表以及辅助数组的空间复杂度为：
O(n+m)
十七、总结
这道题最容易产生的错误是：
尝试搜索从起点到终点的所有路径。
但题目求的并不是普通路径，而是可以重复经过节点和边的旅途，因此旅途数量可能是无限的。
真正的关键是：
在同一个连通块中，我们可以通过绕路经过任意边。
按位与参与的边越多，结果越小，所以同一连通块中任意两个节点之间的最小代价，都是：
这个连通块中所有边权的按位与
因此只需要：
- 用 DFS 划分连通块；
- 用 DFS 计算每个连通块所有边权的按位与；
- 每个询问根据连通块编号直接回答。
这里空空如也
有帮助，赞一个