【题意】
给出一个无向图，有边权，求可以重复走的路径的最大的异或和
【分析】
考虑一个链上出现了一个枝杈挂着一个环，那么枝杈上的边会被走两次，贡献为0，而环上的边却全部能取到
所以我们dfs一次把所有环上的异或和放入线性基
然后随意取一条1-n的链，作为初始值，询问线性基构成的最大异或和即可
至于为什么可以随意选一条链？ 因为如果有多种1-n的链，他们会构成环，被放入线性基，所以其他情况也被考虑在内了
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e4+5; const int maxm=1e5+5; int n,m; ll x; ll p[105],ans; struct point { int to,nxt; ll v; }e[maxm<<1]; int head[maxn],vis[maxn],cnt; void add(int x,int y,ll z) { e[++cnt].to=y; e[cnt].nxt=head[x]; e[cnt].v=z; head[x]=cnt; e[++cnt].to=x; e[cnt].nxt=head[y]; e[cnt].v=z; head[y]=cnt; } ll del[maxn]; void insert(ll x) { for(int i=60;i>=0;i--) if((x>>i)&1) { if(p[i]) x^=p[i]; else { p[i]=x; return; } } } void dfs(int u,ll res) { del[u]=res; vis[u]=1; for(int i=head[u];i;i=e[i].nxt) { int to=e[i].to; if(!vis[to]) dfs(to,res^e[i].v); else insert(res^e[i].v^del[to]); } } ll query(ll x) { ll res=x; for(int i=60;i>=0;i--) if((res^p[i])>res) res^=p[i]; return res; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); 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); } dfs(1,0); printf("%lld\n",query(del[n])); return 0; }
原文：https://www.cnblogs.com/andylnx/p/14824663.html