[BZOJ2115]线性基+dfs树
路径最大异或和问题
嘿嘿，怎么又是dfs树上问题啊，看来线性基喜欢这种类型。
- 简述题意就是：一张无向图，求1~n路径最大权值异或和。
- 先了解到1~n这个路径你可以随意走，不过每个边使用一次就得异或一下它的权值，所以重复走一条边还是可以推成走一次或者没有走。
- 这样的话，路径有很多种，我们一种暴力算法是枚举出所有的路径，取最大值。但显然复杂度太高，如何有效地处理问题呢？
- 我们遇到了瓶颈，所以需要转化思路。画几张图，发现：
- 任意一条1~n的路径，可以看成1到n在dfs树上的链与若干个环异或得到的。
- 那么这题就好写了，我们求出每一个环的权值异或和，然后插入到线性基里面。让ans初始值为链1到n的权值异或和，然后从左向右异或去最大值就ok了。
- 怎样快速求两点之间的路径权值异或和？因为非树边只可能是返祖边，所以只需要dfs的时候更新d【x】表示1~x这条路径的权值异或和，然后求两个点之间的时候异或一下就好了。
Coding
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m,tot,cnt,ver[N],Next[N],lin[N];
ll a[100],b[N],edge[N],f[N];bool v[N];
void add(int x,int y,ll z){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;}
void dfs(int x,int fa,int o){
v[x]=1;f[x]^=f[fa];f[x]^=edge[o];
for(int i=lin[x];i;i=Next[i]){
int y=ver[i];
if(!v[y]){
dfs(y,x,i);
}else if(y!=fa){
cnt++;
b[cnt]^=f[x];
b[cnt]^=f[y];
b[cnt]^=edge[i];
}
}
}
void insert(ll v){
for(int i=63;i>=0;--i) if((v>>i)&1){
if(a[i]) v^=a[i];
else{
for(int j=i-1;j>=0;--j)
if((v>>j)&1) v^=a[j];
for(int j=i+1;j<=63;++j)
if((a[j]>>i)&1) a[j]^=v;
a[i]=v;
break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;ll z;
for(int i=1;i<=m;++i){
scanf("%d%d%lld",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
dfs(1,0,0);
for(int i=1;i<=cnt;++i) insert(b[i]);
ll ans=f[n];
for(int i=63;i>=0;--i) ans=max(ans,ans^a[i]);
printf("%lld\n",ans);
return 0;
}
版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。