题目描述

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

11

表示真,

00

表示假):

QQ20180128145629.png

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

譬如

1212

XOR

99

的计算过程如下:

QQ20180128145728.png

1212

XOR

9=59 = 5

容易验证, XOR 运算满足交换律与结合律,故计算若干个数的 XOR 时,不同的计算顺序不会对运算结果造成影响。从而,可以定义

KK

个非负整数

A1A_1

A2A_2

,……,

AK1A_{K-1}

AKA_K

的 XOR 和为

A1A_1

XOR

A2A_2

XOR …… XOR

AK1A_{K-1}

XOR

AKA_K

考虑一个边权为非负整数的无向连通图,节点编号为

11

NN

,试求出一条从

11

号节点到

NN

号节点的路径,使得路径上经过的边的权值的 XOR 和最大。

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

输入输出格式

输入格式:
输入文件 xor.in 的第一行包含两个整数

NN

MM

, 表示该无向图中点的数目与边的数目。

接下来

MM

行描述

MM

条边,每行三个整数

SiS_i

TiT_i

DiD_i

, 表示

SiS_i

TiT_i

之间存在一条权值为

DiD_i

的无向边。

图中可能有重边或自环。

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

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

【样例说明】

QQ20180128150132.png

如图,路径

124352451 \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 100

M1000M \leq 1000

Di104D_i \leq 10^{4}

对于

50%50 \%

的数据,

N1000N \leq 1000

M10000M \leq 10000

Di1018D_i \leq 10^{18}

对于

70%70 \%

的数据,

N5000N \leq 5000

M50000M \leq 50000

Di1018D_i \leq 10^{18}

对于

100%100 \%

的数据,

N50000N \leq 50000

M100000M \leq 100000

Di1018D_i \leq 10^{18}

首先找到一条1~n的路径 然后把图中所有的环都找出来 插入线性基 然后到时候就用所有的环和1~n的路径贪心xor即可

正确性 首先所有路径都可以表示成过环或者不过 这个如何来看假设环很远 那么我可以到环再走回来看作权值为环xor上路径即可

另外是否任选都可以 考虑如果有两条路径的话 那么他们之间一定会构成环 那么考虑经过这个环然后再走回去再走新的路相当于把原来的路都异或掉了 相当于也是选择了这条路 然后走另外一个环于是可以同理做

 

分类: 线性基贪心

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论