#线性基，深搜#洛谷 4151 最大XOR和路径

本文主要是介绍#线性基，深搜#洛谷 4151 最大XOR和路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

考虑一个边权为非负整数的无向连通图，节点编号为 $1$ 到 $N$，试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得路径上经过的边的权值的 XOR 和最大。

---

分析

首先这个XOR和应该是一条链加上一个个环，异或是可以抵消的，首先链上的东西可以深搜搞定，但是环呢，可以把环的贡献扔到线性基里，最后更新答案即可

---

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long ll; ll rec[61],f[50001];
struct node{int y; ll w; int next;}e[200011];
int n,k=1,ls[50001]; bool v[50001];
inline ll iut(){rr ll ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void add(ll x){for (rr int i=60;i>=0;--i)if ((x>>i)&1){if (!rec[i]){rec[i]=x;return;}x^=rec[i];}
}
inline void dfs(int x,ll now){f[x]=now; v[x]=1;for (rr int i=ls[x];i;i=e[i].next)if (!v[e[i].y]) dfs(e[i].y,now^e[i].w);else add(now^e[i].w^f[e[i].y]);
}
inline ll query(ll x){for (rr int i=60;i>=0;--i)if ((x^rec[i])>x) x^=rec[i];return x;
}
signed main(){n=iut();for (rr int m=iut();m;--m){rr int x=iut(),y=iut(); rr ll w=iut();e[++k]=(node){y,w,ls[x]}; ls[x]=k;e[++k]=(node){x,w,ls[y]}; ls[y]=k;}dfs(1,0);return !printf("%lld",query(f[n]));
}

这篇关于#线性基，深搜#洛谷 4151 最大XOR和路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---