#P4151. [WC2011] 最大XOR和路径

    ID: 4905 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论贪心2011WC/CTSC/集训队枚举,暴力深度优先搜索,DFS线性基向量

[WC2011] 最大XOR和路径

题目描述

XOR(异或)是一种二元逻辑运算,其运算结果当且仅当两个输入的布尔值不相等时才为真,否则为假。 XOR 运算的真值表如下(11 表示真, 00 表示假):

输入 输出
A B A XOR B
0 0
1 1
1 0
1 0

而两个非负整数的 XOR 是指将它们表示成二进制数,再在对应的二进制位进行 XOR 运算。

譬如 1212 XOR 99 的计算过程如下:

$$12=(1100)_2\ \ \ 9=(1001)_2\\ \begin{matrix} &1\ 1\ 0\ 0\\ \text{XOR}&1\ 0\ 0\ 1\\ \hline &0\ 1\ 0\ 1\\ \end{matrix}\\ (0101)_2=5 $$

1212 XOR 9=59 = 5

容易验证, XOR 运算满足交换律与结合律,故计算若干个数的 XOR 时,不同的计算顺序不会对运算结果造成影响。从而,可以定义 KK 个非负整数 A1A_1A2A_2,……,AK1A_{K-1}AKA_K的 XOR 和为

A1A_1 XOR A2A_2 XOR …… XOR AK1A_{K-1} XOR AKA_K

考虑一个边权为非负整数的无向连通图,节点编号为 11NN,试求出一条从 11 号节点到 NN 号节点的路径,使得路径上经过的边的权值的 XOR 和最大。

路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 XOR 和时也要被计算相应多的次数,具体见样例。

输入格式

输入文件 xor.in 的第一行包含两个整数 NNMM, 表示该无向图中点的数目与边的数目。

接下来 MM 行描述 MM 条边,每行三个整数 SiS_iTiT_iDiD_i, 表示 SiS_iTiT_i 之间存在一条权值为 DiD_i 的无向边。

图中可能有重边或自环。

输出格式

输出文件 xor.out 仅包含一个整数,表示最大的 XOR 和(十进制结果)。

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2
6

提示

【样例说明】

如图,路径$1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 5$对应的XOR和为

22 XOR 11 XOR 22 XOR 44 XOR 11 XOR 11 XOR 3=63 = 6

当然,一条边数更少的路径1351 \rightarrow 3 \rightarrow 5对应的XOR和也是22 XOR 4=64 = 6

【数据规模】

对于 20%20 \% 的数据,N100N \leq 100M1000M \leq 1000Di104D_i \leq 10^{4}

对于 50%50 \% 的数据,N1000N \leq 1000M10000M \leq 10000Di1018D_i \leq 10^{18}

对于 70%70 \% 的数据,N5000N \leq 5000M50000M \leq 50000Di1018D_i \leq 10^{18}

对于 100%100 \% 的数据,N50000N \leq 50000M100000M \leq 100000Di1018D_i \leq 10^{18}