跳转至

BZOJ2115 最大异或和路径

题面

给定一个 n(n\le 50000) 个点 m(m\le 10000) 条边的无向图，每条边上有一个权值。

请你求一条从 1 到 n 的路径，使得路径上的边的异或和最大。

题解

这题思想还是不错的。

可以将一条路径拆分成一条1到n的一条路径边权的异或和与一些环的异或和的异或和。

因为如果从1开始走到一个环的起点，将其遍历一遍之后再走回1就相当于获得了这个环的异或和的值。

于是我们先dfs一遍，然后以环的异或和为向量空间，求出线性基\mathfrak{B}，然后取初始答案为dfs后1到n的路径异或和，然后在\mathfrak{B}上从高位到低位贪心的取，如果当前位置异或上答案能够使答案变大就取，否则不取。

Sengxian的证明（我懒得写了）

证明：从高到低考虑每个二进制位，设当前的答案为 s，考虑到第 k 位，线性基向量中代表二进制位 k 的向量为 \mathbf{v}。那么对于第 k位，一共有三种情况，我们分别考虑我们的选择原则是不是正确的。

  1. s 中第 k 位是 1，\mathbf{v} 中第 k 位是 1，实际上不能选。根据我们的选择原则，此时异或起来答案一定会变小，不选。正确。

  2. s 中第 k 位是 0，\mathbf{v} 中第 k 位是 1，实际上要选。根据我们的选择原则，此时异或起来答案一定会变大，选。正确。

  3. \mathbf{v} 中第 k 位是 0，那么 \mathbf{v} 必定是零向量，选不选无所谓。正确。

所以在每一种情况中，我们的选择原则都是正确的，所以这个贪心也是正确的。

程序

 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MAX_N 100007
#define MAX_M 200007
#define reg register
typedef unsigned long long ll;

int N, M;
int head[MAX_N], to[MAX_M], nxt[MAX_M], cap;
int fa[MAX_N];
ll dis[MAX_M], d[MAX_N], a[MAX_M], b[65], top, res;
int vis[MAX_N], dfn;

template <typename _T> inline void read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-') y = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
}

inline void addEdge (int u, int v, ll w) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
    dis[cap] = w;
}

void dfs (int x) {
    if (vis[x]) return;
    vis[x] = ++dfn;
    for (int i = head[x]; i; i = nxt[i])
        if (!vis[to[i]]) {
            fa[to[i]] = x;
            d[to[i]] = d[x] ^ dis[i];
            dfs(to[i]);
        } else if (vis[to[i]] && to[i] != fa[x]) {
            a[++top] = d[x] ^ d[to[i]] ^ dis[i];
        }
}

inline void makeBase () {
    for (int i = 1;i <= top; ++i)
        for (int j = 63; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k)
                        if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= 63; ++k)
                        if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
}

inline void solve () {
    res = d[N];
    for (int i = 64; i >= 0; --i) {
        if (b[i] == 0) continue;
        if ((res ^ b[i]) > res) res ^= b[i];
    }
    printf("%lld\n", res);
}

int main () {
    read(N), read(M);
    int u, v;
    ll w;
    for (int i = 1; i <= M; ++i) {
        read(u), read(v), read(w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    dfs(1);
    makeBase();
    solve();
    return 0;
}