P14994 异或最短路和 题解
flywen
·
·
题解
不会线性基的看这里——《初中生都能看懂的线性基详解》，以下内容均来自我的这篇专栏。
P4151 [WC2011] 最大 XOR 和路径 / CF845G Shortest Path Problem?
给定一张 n 个点 m 条边的带权无向连通图，求 1 号点到 n 号点的（非简单）路径异或和最大 / 小值。
---
考虑求一个生成树，对于点 $u$ ，其到 $1$ 号点的树边异或和为 $d_u$。对于所有非树边 $(u,v)$，它都对应着一个环 $u\rightarrow1\rightarrow v\rightarrow u$，其权值为 $d_u\oplus d_v\oplus w_{u\rightarrow v}$，发现仅使用这些环，能够线性组合出其它的环，因为走过一条边两次相等于没有走。
将上述所有非树边所对的环加入线性基，最后答案为 $d_n$ 在线性基中的最大 / 小表示。
时间复杂度 $O(m\log V)$。
```cpp
vector<pair<int,ll>>e[N];
void dfs(int u){
vst[u]=1;
for(int i=0;i<e[u].size();++i){
int v=e[u][i].first;ll w=e[u][i].second;
if(vst[v])L.insert(d[u]^d[v]^w);
else{
d[v]=d[u]^w;
dfs(v);
}
}
}
```
---
### [P14994 异或最短路和](https://www.luogu.com.cn/problem/P14994)
给定一张 $n$ 个点 $m$ 条边的带权无向图，求对于每个有序点对之间（非简单）路径异或和最小值之和：
$$\sum_{u=1}^n\sum_{v=1}^n\operatorname{dist}(u,v)$$
若 $u,v$ 无法互达，$\operatorname{dist}(u,v)=0$。
$n,m\leq2\times10^5,V\leq10^{18}$。
---
若 $u,v$ 可达，则 $\operatorname{dist}(u,v)$ 是 $d_u\oplus d_v$ 在该连通块中所有环构成的线性基中的最小表示。考虑快速计算。
介绍一个性质，假设 $f(x)$ 为 $x$ 在线性基的最小表示， 那么有：
$$f(x\oplus y)=f(x)\oplus f(y)$$
按位考虑，分类讨论易证。
那么原式可以按位计算，时间复杂度 $O((n+m)\log V)$。
```cpp
for(int k=0;k<vec.size();++k){ //枚举连通块内的点
int i=vec[k];
f[i]=L.minrep(d[i]);
for(int j=0;j<V;++j)if(f[i]&(1ll<<j))++c[j]; //统计每一位1的个数
}
for(int k=0;k<vec.size();++k){
int i=vec[k];
for(int j=0;j<V;++j){
if(f[i]&(1ll<<j))ans=(ans+(1ll<<j)*(vec.size()-c[j])%mod)%mod;
else ans=(ans+(1ll<<j)*c[j]%mod)%mod;
}
}
```