线性基与图论结合的经典问题
立体传送门：Luogu P4151
不急，一步一步来。
第一种情况，考虑我们现在已经有一条 \(1-> n\) 的路径，不妨设为 \(1->i->j->k->n\)，异或起来为 \(dis_n\)，那么我们的 \(ans\) 就是 \(dis_n\)。
第二种情况，在上种情况基础上，考虑这条路径上的 \(i\) 点有个环，不妨设这个环的异或起来为 \(I\)，那么我们的 \(ans\) 就是 \(min(dis_n,dis_n\oplus I)\)，即：走不走这个环。
第三种情况，在上种情况的基础上，考虑这条路径上的 \(j\) 有条到 \(a\) 的路径，然后 \(a\) 点上有个环，不妨设 \(j\) 连向 \(a\) 的路径异或起来是 $ J$，这个环异或起来为 \(A\)，那么我们的 \(ans\) 就是 \(min(ans,ans\oplus J\oplus A\oplus J)\)，即 \(min(ans,ans\oplus A)\)，我们发现，这种情况跟第二种情况差不多，只需要知道整个环的异或值即可
第四种情况，在上种情况的基础上，考虑有条边为 \(k->i\)，即有个环为 \(i->j->k->i\)，不妨设该环的异或值为 \(K\)，那我们的 \(ans\) 就是 \(min(ans,ans\oplus K)\)，因为是无向边，所以从 \(i\) 到 \(k\) 的边有两条，为 \(i->j->k\) 和 \(i->k\) ，而\(ans\oplus K\) 就是走 \(i->k\) 这条。
我们发现：
1、对于第一种情况，我们只需要找到随便一条到达 \(n\) 的路径即可。对于第二到第四种情况，只要求出环的异或值即可。
2、上面四种情况包含了所有的图，只是数量更多罢了。
那么我们就可以根据发现的规律推做法：
对于发现 \(1\)，我们可以用 \(dfs\) 找路径和环的异或值。
对于发现 \(2\)，我们可以用线性基去做，求出在原来路径的基础上，走哪些环可以使异或值更大
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=250000;
ll n,m;
ll h[N],e[N],w[N],ne[N],idx;
void add(ll a,ll b,ll c)
{
e[++idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
}
ll dis[N],num[N];
bool vis[N];
void insert(ll x)
{
for(ll i=63;i>=0;i--)
if((1ll<<i)&x)
{
if(!num[i]) num[i]=x;
x^=num[i];
}
}
ll query(ll x)
{
ll re=x;
for(ll i=63;i>=0;i--)
if((re^num[i])>re)
re^=num[i];
return re;
}
void dfs(ll wz,ll res)
{
dis[wz]=res;
vis[wz]=true;
for(ll i=h[wz];i!=-1;i=ne[i])
if(!vis[e[i]]) dfs(e[i],res^w[i]);
else insert(res^w[i]^dis[e[i]]);
}
int main()
{
memset(h,-1,sizeof h);
scanf("%lld %lld",&n,&m);
ll t1,t2,t3;
for(ll i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&t1,&t2,&t3);
add(t1,t2,t3);
add(t2,t1,t3);
}
dfs(1,0);
printf("%lld\n",query(dis[n]));
return 0;
}