题目
题目描述
XOR（异或）是一种二元逻辑运算，其运算结果当且仅当两个输入的布尔值不相等时才为真，否则为假。 XOR 运算的真值表如下（$1$表示真，$0$表示假）：
而两个非负整数的 XOR 是指将它们表示成二进制数，再在对应的二进制位进行 XOR 运算。
譬如$12$XOR$9$的计算过程如下：
故$12$XOR$9$=$5$。
容易验证， XOR 运算满足交换律与结合律，故计算若干个数的 XOR 时，不同的计算顺序不会对运算结果造成影响。从而，可以定义$K$个非负整数 $A_1,A_2,A_3,A_4…A_{K-1},A_K$的 XOR 和为$A_1$XOR$A_2$XOR$A_3…$XOR$A_K$
考虑一个边权为非负整数的无向连通图，节点编号为$1$到$N$，试求出一条从$1$号节点到$N$号节点的路径，使得路径上经过的边的权值的 XOR 和最大。
路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数，具体见样例。
输入输出格式
输入格式：
输入文件 xor.in 的第一行包含两个整数$N$和$M$，表示该无向图中点的数目与边的数目。
接下来$M$行描述$M$条边，每行三个整数$S_i,T_i,D_i$，表示$S_i$与$T_i$之间存在一条权值为$D_i$的无向边。
图中可能有重边或自环。
输出格式：
输出文件 xor.out 仅包含一个整数，表示最大的 XOR 和（十进制结果）。
输入输出样例
输入样例#1：
5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2
输出样例#1：
6
说明
【样例说明】
如图，路径$1→2→4→3→5→2→4→5$对应的XOR和为$2$XOR$1$XOR$2$XOR$4$XOR$1$XOR$1$XOR$3=6$
当然，一条边数更少的路径$1→3→5$对应的XOR和也是$2$XOR$4=6$。
【数据规模】
对于$20\%$的数据，$N\leq 100$，$M\leq 1000$，$D_i\leq 10^4$
对于$50\%$的数据，$N\leq 1000$，$M\leq 10000$，$D_i\leq 10^{18}$
对于$70\%$的数据，$N\leq 5000$，$M\leq 50000$，$D_i\leq 10^{18}$
对于$100\%$的数据，$N\leq 50000$，$M\leq 100000$，$D_i\leq 10^{18}$
题解
因为是求XOR最大一下就想到线性基
但是这是在图里该怎么解决呢？
因为XOR的性质，一条边走两次就相当于没走
题目中还有：
路径可以重复经过某些点或边
所以一条路径可以通过经过XOR一堆环成为另一条路径这样子
所以可以找到所有的环和任意一条路径然后用线性基求一下最大值
$dfs$找环，并储存一条路径的XOR值
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# define LL long long
using namespace std;
const int MAX=1e5+1,MAXN=64;
struct p{
int x,y;
LL dis;
}c[MAX<<1];
int n,m,num,tot;
int h[MAX];
LL a[MAX<<4],b[MAXN],d[MAX];
bool use[MAX];
void add(LL dis,int x,int y)
{
c[++num]=(p){h[x],y,dis},h[x]=num;
c[++num]=(p){h[y],x,dis},h[y]=num;
}
LL read()
{
LL x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void dfs(int x)
{
for(int i=h[x];i;i=c[i].x)
if(!use[c[i].y])
{
use[c[i].y]=1,d[c[i].y]=d[x]^c[i].dis;
dfs(c[i].y);
}
else a[++tot]=d[x]^c[i].dis^d[c[i].y];
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;++i)
add(read(),read(),read());
use[1]=1,dfs(1);
LL ans=d[n];
for(int i=1;i<=m;++i)
for(int j=63;~j;--j)
if(a[i]&(1ll<<j))
{
if(!b[j])
{
b[j]=a[i];
break;
}
else a[i]^=b[j];
}
for(int i=63;~i;--i)
if((ans^b[i])>ans) ans^=b[i];
return printf("%lld",ans),0;
}
