bzoj#P2115. [Wc2011] Xor
[Wc2011] Xor
题目描述
XOR(异或)是一种二元逻辑运算,其运算结果当且仅当两个输入的布尔值不相等时才为真,否则为假。 XOR 运算的真值表如下( 表示真, 表示假):
输入 | 输出 | |
---|---|---|
A | B | A XOR B |
0 | 0 | |
1 | 1 | |
1 | 0 | |
1 | 0 |
而两个非负整数的 XOR 是指将它们表示成二进制数,再在对应的二进制位进行 XOR 运算。
容易验证, XOR 运算满足交换律与结合律,故计算若干个数的 XOR 时,不同的计算顺序不会对运算结果造成影响。从而,可以定义 个非负整数 ,,……,,的 XOR 和为
XOR XOR …… XOR XOR
考虑一个边权为非负整数的无向连通图,节点编号为 到 ,试求出一条从 号节点到 号节点的路径,使得路径上经过的边的权值的 XOR 和最大。
路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 XOR 和时也要被计算相应多的次数,具体见样例。
输入格式
第一行包含两个整数 和 , 表示该无向图中点的数目与边的数目。
接下来 行描述 条边,每行三个整数 , , , 表示 与 之间存在一条权值为 的无向边。
图中可能有重边或自环。
输出格式
输出仅包含一个整数,表示最大的 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
提示
对于 的数据,, ,;
对于 的数据,, ,;
对于 的数据,, ,;
对于 的数据,, ,。
题目来源
WC2011