P4151 [WC2011]最大XOR和路径

    • 293通过
    • 725提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 图论 深度优先搜索,DFS 线性基 贪心 WC/CTSC/集训队 2011 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    QQ20180128145629.png

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

    譬如 $12$ XOR $9$ 的计算过程如下:

    QQ20180128145728.png

    故 $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 和时也要被计算相应多的次数,具体见样例。

    输入输出格式

    输入格式:

    输入文件 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

    说明

    【样例说明】

    QQ20180128150132.png

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

    $2$ XOR $1$ XOR $2$ XOR $4$ XOR $1$ XOR $1$ XOR $3 = 6$

    当然,一条边数更少的路径 $1 \rightarrow 3 \rightarrow 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}$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。