题面

样例输入

第一行包含两个整数$N$和 $M$， 表示该无向图中点的数目与边的数目。 接下来$M$ 行描述 $M$ 条边，每行三个整数$S_i$，$T_i$ ，$D_i$，表示 $S_i$ 与$T_i$之间存在 一条权值为 $D_i$的无向边。 图中可能有重边或自环。

样例输出

仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

思路

真是一道代码极短思维难度高的题目。我们考虑异或的性质，这题边可以走多次，那么我们考虑把图中的每个环的异或和都加入线性基。并将随便一条1到N的简单路径的异或和加入，具体情况看图。

代码

#include<bits/stdc++.h>
#define Maxn 50005
#define Maxm 100005
#define LL long long
LL N,M,head[Maxn],dis[Maxn],cnt=0,p[65];
bool vis[Maxn];
struct edge{LL next,to,dis;}e[Maxm<<1];
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void add(LL x,LL y,LL z){e[++cnt].next=head[x];e[cnt].to=y;e[cnt].dis=z;head[x]=cnt;}
inline void insert(LL x)
{
	for (LL i=62;i>=0;i--)
	{
		if (!(x>>i&1)) continue;
		if (!p[i]) {p[i]=x;return;}
		x^=p[i];
	}	
} 
inline void dfs1(LL now,LL fa)
{
	vis[now]=1;
	for (LL i=head[now];i;i=e[i].next)
	{
		LL v=e[i].to;
		if (v==fa) continue;
		if (!vis[v]) {dis[v]=dis[now]^e[i].dis;dfs1(v,now);}
		else insert(dis[now]^dis[v]^e[i].dis);
	}
}
int main()
{
	read(N),read(M);
	for (LL i=1;i<=M;i++) 
	{
		LL s,t,d;
		read(s),read(t),read(d);
		add(s,t,d),add(t,s,d);
	}
	dfs1(1,1);
	LL ans=dis[N];
	for (LL i=62;i>=0;i--) if ((ans^p[i])>ans) ans^=p[i];
	cout<<ans<<endl;
	return 0;
}