题目概述

给出一张有边权的无向图，求从 $1$ 到 $n$ 路径异或最大值，可以重复走点并且可以重复经过 $n$ 。

解题报告

好妙的题！无向图中的环是可以经过也可以不经过的，所以我们可以把所有环加入线性基。那么现在的问题就是如何选取环使得异或和最大，可以想到枚举一条路径并把路径上能够经过的环加入线性基，然后用线性基就可以求出这条路径的最大值。

然而复杂度飞天了，怎么办呢？我们发现如果如果有多条路径都能从 $1$ 到 $n$ ，那么就形成了若干个环，所以干脆随便选出一条 $1$ 到 $n$ 的路径，做全图环的线性基就行啦。

但是这样有个问题，可能会出现路径和环不交的情况！实际上因为可以重复走，所以可以强行走到环再走回来……异或和不变。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=50000,maxm=200000,Log=60;

int n,m;LL sum[maxn+5],M[Log+5],ans;bool vis[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5];LL w[maxm+5];

#define Add(x,y,z) (son[E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E++)
inline void Insert(LL x) {for (int j=Log;~j;j--) if (x>>j&1) if (!M[j]) {M[j]=x;break;} else x^=M[j];}
void Dfs(int x,int pre=-1){
    for (int j=(vis[x]=true,lnk[x]);~j;j=nxt[j])
        if (j^1!=pre) if (vis[son[j]]) Insert(sum[x]^sum[son[j]]^w[j]);
        else if (!vis[son[j]]) sum[son[j]]=sum[x]^w[j],Dfs(son[j],j);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=m;i++) {int x,y;LL z;scanf("%d%d%lld",&x,&y,&z),Add(x,y,z),Add(y,x,z);}
    Dfs(1);ans=sum[n];for (int j=Log;~j;j--) if ((ans^M[j])>ans) ans^=M[j];printf("%lld\n",ans);return 0;
}