题解：AT_abc408_e [ABC408E] Minimum OR Path

· · 题解

原题

题意

给定一张连通无向图，找从 1 到 n 的简单路径，使得路径上所有边权按位或的结果尽可能小。

思路

先看按位或运算的特点，只要二进制某一位出现过一次 1，最后结果里这一位就一定是 1，没办法再变回 0。

从这个性质能看出来，想要让最终或运算结果最小，就得优先让高位尽量是 0，高位能不用 1 就不用，比纠结低位划算很多。

顺着这个规律，就能想到用按位贪心的思路来做。

一开始先把答案初始化成 30 位二进制全为 1，再从最高位往低位挨个尝试，看看这一位能不能不用取 1。

判断方法也很简单：

先临时把当前这一位当作 0，定下一个上限值。

只要图里还存在一条从 1 走到 n 的路线，并且路线里每条边，和这个上限值做或运算后都不会超过上限，就说明这一位完全可以不用设成 1；

如果找不到这样的路径，那就只能保留这一位为 1。

时空复杂度

时间复杂度：$O(W(n + m))

空间复杂度：O(n + m)

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 2e5 + 5;

int n, m, ans = (1 << 30) - 1, v[N];
vector<pii> g[N];

void dfs(int u, int c) {                        // 只走不会超出限定或值的边
  v[u] = 1;                                     // 标记已经走过
  for (pii i : g[u]) {
    if ((i.second | c) == c && !v[i.first]) {   // 边权或起来不超限制就可以走
      dfs(i.first, c);
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    g[u].push_back({v, w}), g[v].push_back({u, w});
  }
  for (int i = 29; i >= 0; i--) {               // 从高位往低位逐个贪心
    fill(v + 1, v + n + 1, 0);                  // 每次清空访问标记
    dfs(1, ans - (1 << i));                     // 试着把当前位不计入答案
    ans -= (1 << i) * v[n];                     // 能到终点就直接舍去这一位
  }
  cout << ans;
  return 0;
}