d998: WC2011 1.最大XOR和路径
標籤 :
通過比率 : 86% (31 人 / 36 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-02-21 19:11

內容

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

 


而两个非负整数的XOR 是指将它们表示成二进制数,再在对应的二进制位进行XOR 运算。
譬如12 XOR 9 的计算过程如下 :

 

故12 XOR 9 = 5。
容易验证,XOR 运算满足交换律与结合律,故计算若干个数的XOR 时,不同的计算顺序不会对运算结果造成影响。从而,可以定义K 个非负整数
A_1,A_2...A_k-1,A_k的XOR 和为
A_1 XOR A_2 XOR … XOR A_k-1 XOR A_k
考虑一个边权为非负整数的无向连通图,节点编号为1 到N,试求出一条从1 号节点到N 号节点的路径,使得路径上经过的边的权值的XOR 和最大。
路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算XOR 和时也要被计算相应多的次数,具体见样例。

輸入說明

输入文件的第一行包含两个整数N 和M,表示该无向图中点的数目与边的数目。
接下来M 行描述M 条边,每行三个整数Si,Ti ,Di,表示Si 与Ti 之间存在一条权值为Di 的无向边。
图中可能有重边或自环。

輸出說明

输出文件仅包含一个整数,表示最大的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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 :

【样例说明】

 

如图,路径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<=100,M<=1000,Di<=10^4
对于50%的数据,N<=1000,M<=10000,Di<=10^18
对于70%的数据,N<=5000,M<=50000,Di<=10^18
对于100%的数据,N<=50000,M<=100000,Di<=10^18

標籤:
出處:
WC2011第一题 [編輯:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
15017
dimitryl (dimitryl)
d998
主體思路
130 2018-08-31 22:20