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}$ 必定是零向量,选不选无所谓。正确。

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

程序

#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;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注