题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2115

题目分类：高斯消元，数论

题意：

给出一个图，求一条从1到n的路径使得该路径的异或和最大。

题解：

求出图中的环，可以发现从1到n的路径实际上是走一条无环路径加上若干个环的异或值，因为从无环路径到环和从环回来的两部分可以抵消，相当于给出一个集合的数，选出一部分使得和某一个数异或起来最大。

发现对于一个集合，把他们互相异或之后得到的集合可以异或出来的值和原集合可以异或出来的值是一样的。所以可以进行高斯消元使得每一位只在一个数中出现过，这样从高位到低位贪心就可以求出最大值。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
long long ed,st[2600000];
struct node
{
	long long to,next;
	long long va;
}g[2600000];
inline void add(long long x,long long y,long long z)
{
	ed++;
	g[ed].to=y;
	g[ed].next=st[x];
	g[ed].va=z;
	st[x]=ed;
}
long long vis[2600000],num;
long long n,m,x1,x2;
long long x3;
long long dis[2600000],cir[2600000];
inline void dfs(long long x)
{
	vis[x]=1;
	for (long long i=st[x];i!=0;i=g[i].next)
	{
		if(vis[g[i].to]==0)
		{
			dis[g[i].to]=(dis[x]^g[i].va);
			dfs(g[i].to);
		}
		else
		{
			num++;
			cir[num]=(dis[g[i].to]^dis[x]^g[i].va);
		}
	}
}
inline long long gauss()
{
	long long k=1;
	for (long long p=63;p>=0;p--)
	{
		long long t=0;
		for (long long j=k;j<=num;j++)
		{
			if((cir[j]&(1LL<<p))!=0){t=j;break;}
		}
		if(t!=0)
		{
			swap(cir[t],cir[k]);
			for (long long j=1;j<=num;j++)
			{
				if(j!=k&&(cir[j]&(1LL<<p))!=0)cir[j]^=cir[k];
			}
			k++;
		}
	}return k-1;
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for (long long i=1;i<=m;i++)
	{
		scanf("%lld %lld %lld",&x1,&x2,&x3);
		add(x1,x2,x3);
		add(x2,x1,x3);
	}
	dfs(1);
	long long cnt=gauss();
	long long ans=dis[n];
	for (long long i=1;i<=cnt;i++)
	{
		if((ans^cir[i])>ans)ans^=cir[i];
	}printf("%lld\n",ans);
	return 0;
}