题解 P4151 【[WC2011]最大XOR和路径】
An_Account
2018-07-13 08:48:57
[我的主页(阅读效果更好)打开即可$RP++$](https://www.luogu.org/space/show?uid=39914)
题目要求很多条边的最大异或和,从这一点我们可以想到线性基。这里归纳一下线性基的几点性质:
设$V$是某个神奇的向量空间,$B$是$V$的基,则$B$应满足以下条件:
> 1.$V$是$B$的极小生成集,就是说只有$B$能张成$V$,而它的任何真子集都不张成全部的向量空间。
> 2.$B$是$V$中线性无关向量的极大集合,就是说$B$在$V$中是线性无关集合,而且$V$中没有其他线性无关集合包含它作为真子集。
> 3.$V$中所有的向量都可以按唯一的方式表达为$B$中向量的线性组合。
这也就是说,我们可以用不超过$log_{2}{m}$个基就能表示所有的异或和,考虑题目中一句重要的话:
> 路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 XOR 和时也要被计算相应多的次数
这句话给了我们一点启发,假设某条路$k$被重复走了两次,那么它的权值对答案的贡献就是$0$,但是通过这条路径$k$,我们可以到达它连接的另一个点。
显然我们没法枚举$1$~$N$的每一条路,但我们可以将路径拆成两部分,第一部分是环,第二部分是链。
假设我们选择了一条从$1$~$N$的链,当然,它不一定是最优秀的。但是别忘了,我们可以选择一些环来增广这条链。举个例子:
![](http://wx3.sinaimg.cn/mw690/0060lm7Tly1ft7x5h09fvj30ir090weg.jpg)
假设$k$是连接这条链和某个环的某条路径,那么显然,链和环都将走过一遍,而这条路径$k$会被走过两遍(从链到环一遍,从环到链一遍)。根据我们上面的推论,$k$对答案的贡献是$0$。于是我们发现,我们根本就没有必要算出这条路径$k$!(反正贡献是$0$)
于是我们枚举所有环,将环上异或和扔进线性基,然后用这条链作为初值,求线性基与这条链的最大异或和。
``` cpp
void dfs(int u,LL res) {//枚举所有环
del[u]=res,vis[u]=1;
for (int i=head[u];i;i=e[i].next)
if (!vis[e[i].to]) dfs(e[i].to,res^e[i].w);
else insert(res^e[i].w^del[e[i].to]);
}
LL query(LL x) {//最大异或和
LL res=x;
for (int i=63;i>=0;i--)
if ((res^num[i])>res)
res^=num[i];
return res;
}
```
最后说一下怎么选最开始的这条链,其实**它可以随便选**。我们考虑以下这种情况:
![](http://wx4.sinaimg.cn/mw690/0060lm7Tly1ft7xo17vhuj30if09xmx5.jpg)
假设路径$A$比路径$B$优秀一些,而我们最开始选择了路径$B$。显然,$A$与$B$共同构成了一个环。如果我们发现路径$A$要优秀一些,那么我们用$B$异或上这个大环,就会得到我们想要的$A$!
所以这道题的算法是:找出所有环,扔进线性基,随便找一条链,以它作为初值求最大异或和就可以了。
附上AC代码:
``` cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
LL num[70];
bool insert(LL x) {
for (int i=63;i>=0;i--)
if ((x>>i)&1) {
if (!num[i]) {
num[i]=x;
return true;
}
x^=num[i];
}
return false;
}
LL query(LL x) {
LL res=x;
for (int i=63;i>=0;i--)
if ((res^num[i])>res)
res^=num[i];
return res;
}
struct edge {
int to,next;
LL w;
}e[200010];
int head[50010],ecnt;
inline void adde(int from,int to,LL w) {
e[++ecnt]=(edge){to,head[from],w},head[from]=ecnt;
e[++ecnt]=(edge){from,head[to],w},head[to]=ecnt;
}
int vis[50010];LL del[50010];
void dfs(int u,LL res) {
del[u]=res,vis[u]=1;
for (int i=head[u];i;i=e[i].next)
if (!vis[e[i].to]) dfs(e[i].to,res^e[i].w);
else insert(res^e[i].w^del[e[i].to]);
}
int main() {
int n,m,a,b;LL c;scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) scanf("%d%d%lld",&a,&b,&c),adde(a,b,c);
dfs(1,0);
printf("%lld\n",query(del[n]));
}
```