BZOJ2115 [Wc2011] Xor
找到了一个不错的题，题目中说要让路径异或和最大，考虑由于路径非常复杂，所以不太可能按照某一路径进行dp，一般对于异或和的操作我们进行线性基，最后答案的路径一定是一条从1到n的路径加上几个环构成，我们dfs找出环来，记录每一个环的异或和，我们可以随意选取一条从1到n的路径当作初始答案去进行线性基，因为如果有多条路径从1到n的话我们选择的路径不是最优解，那么这也就构成了环，我们走一下环，就可以消除我们一开始选择错误路径的影响，所以直接线性基然后求最大值即可。 —— by VANE
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50105; const int M=200105; int n,m,l,cnt; ll last[N],pre[M],other[M]; ll p[100],c[M],ans,w[M],dx[N]; bool vis[N]; void add(ll x,ll y,ll z) { ++l;pre[l]=last[x]; last[x]=l;other[l]=y; w[l]=z; } void dfs(int x) { vis[x]=1; for(int p=last[x];p;p=pre[p]) { int y=other[p]; if(!vis[y]) dx[y]=dx[x]^w[p],dfs(y); else c[++cnt]=dx[x]^dx[y]^w[p]; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c); add(a,b,c);add(b,a,c); } dfs(1); ans=dx[n]; for(int i=1;i<=cnt;++i) for(int j=62;j>=0;--j) { if(!(c[i]>>j)) continue; if(!p[j]){p[j]=c[i];break;} c[i]^=p[j]; } for(int i=62;i>=0;i--) ans=max(ans,ans^p[i]); cout<<ans<<endl; }