[WC2011]最大XOR和路径

题目描述

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

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

输入格式

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

接下来 $M$M 行描述 $M$M 条边，每行三个整数 $S_i$Si​， $T_i$Ti​， $D_i$Di​ ， 表示 $S_i$Si​ 与 $T_i$Ti​ 之间存在一条权值为 $D_i$Di​的无向边。

图中可能有重边或自环。

输出格式

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

说明/提示

对于 $20 \%$20%的数据， $N \leq 100$N≤100， $M \leq 1000$M≤1000， $D_i \leq 10^{4}$Di​≤104；

对于 $50 \%$50%的数据， $N \leq 1000$N≤1000， $M \leq 10000$M≤10000， $D_i \leq 10^{18}$Di​≤1018；

对于 $70 \%$70%的数据， $N \leq 5000$N≤5000， $M \leq 50000$M≤50000， $D_i \leq 10^{18}$Di​≤1018 ；

对于 $100 \%$100%的数据， $N \leq 50000$N≤50000， $M \leq 100000$M≤100000， $D_i \leq 10^{18}$Di​≤1018。

题解

容易发现，这题中的路径价值可以计算为一条从 $1$1到 $N$N的路径与任意个环的异或和

例：

这是一条路径

我们往里面加入一个环：

然后重复的路径因为被异或了两次于是就抵消了：

所以最后的答案就是一条从 $1$1到 $N$N的路径加上任意个环。

枚举所有环的复杂度并不是多项式的，但是我们可以考虑环接环的情况:

同样，重复的路径抵消了：

发现变成了一个大环，这也就说明了任意一个可以被其他环组成的环都不用计算进答案，比如在这个例子中，你只需要计算红环蓝环和最终的大环中的任意两个，就可以顺带把另外一个计算进答案。

于是，我们选择一个策略：随机生成一个生成树，把所有含一条非树边的环算入答案。

至于从一些数里面挑选任意个求最大的异或和可以用线性基解决。