题解：P12259 [蓝桥杯 2024 国 Java B] 最优路径

Yannik · 2025-07-14 22:53:37 · 题解

题意：

任意选两个不同的点使得其路径的异或和最小。求出这个值。

思路：

先考虑任意两个点 x 到 y 的任意一条简单路径。可以通过直接遍历得到，再考虑如何是异或和最小。必然是多走一些路。一个可行的方法是：从某一个点开始走到一个环，在环上走一圈，回到这个点。然后枚举所有环，把环的异或值插入线性基，用线性基跑最小值即可。

Tips：

• 求任意两点简单路径异或和：比如 a 到 b 的异或和为 x，a 到 c 的异或和为 y。则 b 到 c 的异或和为 x ⊕ y。
• 那么一个环的异或和呢？把上面那个 c 改成 b 即可。即 b 再走回 b，不就是一个环吗？

  void dfs(int u,int fa){
  for(auto x:g[u]){
      int e=x.first,w=x.second;
      if(vis[e]){
          ins(xo[e]^xo[u]^w);//环的异或和
      } else {
          vis[e]=1;
          tmp.push_back(e);
          xo[e]=xo[u]^w;
          dfs(e,u);
      }
  }
  }

• 注意两个点之间可能不连通。需要多次遍历。
• 线性基求最小值贪心即可。

  int res=xo[x]^xo[y];
  for(int k=31;~k;k--){
  if((res^p[k])<res) res=res^p[k];
  }
  ans=min(ans,res);

  \tiny 谢谢你的观看。