「BZOJ2115」[WC2011] Xor

Description

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

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

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

Input

输入文件 xor.in 的第一行包含两个整数 NNMM, 表示该无向图中点的数目与边的数目。
接下来 MM 行描述 MM 条边,每行三个整数 SiS_iTiT_iDiD_i, 表示 SiS_iTiT_i 之间存在一条权值为 DiD_i 的无向边。
图中可能有重边或自环。

Output

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

Sample Input

1
2
3
4
5
6
7
8
5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

1
6

HINT


如图,路径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 100M1000M \leq 1000Di104D_i \leq 10^{4}
对于 50%50 \% 的数据,N1000N \leq 1000M10000M \leq 10000Di1018D_i \leq 10^{18}
对于 70%70 \% 的数据,N5000N \leq 5000M50000M \leq 50000Di1018D_i \leq 10^{18}
对于 100%100 \% 的数据,N50000N \leq 50000M100000M \leq 100000Di1018D_i \leq 10^{18}

Solution

Orz(An_Account)

跑出所有的环的异或和,然后插入线性基。
答案就是从11nn任意一条路径的异或和,异或上线性基里能组成的最大值。
图中kk是走了两次所以没有贡献。

为什么可以任意选一条边呢?

如果路径AA比路径BB更加优秀,而我们却选择了BB,显然AABB构成了一个大环,如果BB异或上这个大环就是AA了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 51000, M = 210000;
struct Edge {
int u, v, nxt;
ll w;
}e[M];
int head[N], en;
void addedge(int x, int y, ll z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
int n, m;
bool vis[N];
ll v[N];
ll p[70];
void ins(ll val) {
for(int i = 63; ~i; --i)
if(val & (1ll << i)) {
if(!p[i]) {
p[i] = val;
break;
} else val ^= p[i];
}
}
ll ans;
void dfs(int x, ll c) {
vis[x] = 1;
v[x] = c;
if(x == n) ans = c;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(vis[y]) ins(v[x] ^ e[i].w ^ v[y]);
else dfs(y, c ^ e[i].w);
}
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
ll z = read();
addedge(x, y, z);
addedge(y, x, z);
}
dfs(1, 0);
for(int i = 63;~i; --i)
if((ans ^ p[i]) > ans) ans ^= p[i];
writeln(ans);
return 0;
}