bzoj 2115 [Wc2011] Xor 路径最大异或和 线性基

题目链接

题意

给定一个 \(n(n\le 50000)\) 个点 \(m(m\le 100000)\) 条边的无向图，每条边上有一个权值。请你求一条从 \(1\)到\(n\)的路径，使得路径上的边的异或和最大。

题解

参考

https://blog.sengxian.com/algorithms/linear-basis

结论

答案=\(max_\{\)(某一条\(1\)到\(n\)的路径的异或和)\(\oplus\)(环\(i_1\)的异或和)\(\oplus\)(环\(i_2\)的异或和)...\(\}\)

构造性证明

我们证明，对于图中任意一个环，其异或和是可以取到的。

方法是从任意一个点\(u\)出发走到环上的某一点\(v\)，绕一圈，然后再沿着\(v\)到\(u\)的路径原路返回，记路径\(u\rightarrow v\)的异或和为\(x_0\)，环上的异或和为\(x_1\)，则这一整段路的贡献即为\(x_0\oplus x_1\oplus x_0=x_1\)，即为环上的异或和。

求值

现在的问题就转化为了，在线性基中取若干个向量，使得它们与某个初始给定值的异或和取到最大。

将向量从高位向低位逐个加入，使得和变大则加，否则不加，即可取到最大。

由线性基线性无关易见，对某一位的贡献只能来自于最多一个向量。

Code

#include <bits/stdc++.h>

#define maxn 200010

#define maxl 60

using namespace std;

typedef long long LL;

struct Edge { int to, ne; LL d; } edge[maxn<<1];

LL d[maxn], b[maxn];

int tot, ne[maxn], cnt;

bool vis[maxn];

void add(int u, int v, LL d) {

    edge[tot] = {v, ne[u], d};

    ne[u] = tot++;

    edge[tot] = {u, ne[v], d};

    ne[v] = tot++;

}

void dfs(int u, LL dd) {

    d[u] = dd; vis[u] = true;

    for (int i = ne[u]; ~i; i = edge[i].ne) {

        int v = edge[i].to;

        if (vis[v]) b[cnt++] = d[u] ^ edge[i].d ^ d[v];

        else dfs(v, d[u] ^ edge[i].d);

    }

}

struct LinearBasis {

    LL a[maxl+1];

    LinearBasis() { memset(a, 0, sizeof a); }

    void insert(LL t) {

        for (int i = maxl; i >= 0; --i) {

            if (!(t >> i & 1)) continue;

            if (a[i]) t ^= a[i];

            else {

                for (int j = 0; j < i; ++j) if (t >> j & 1) t ^= a[j];

                for (int j = i+1; j <= maxl; ++j) if (a[j] >> i & 1) a[j] ^= t;

                a[i] = t;

                return;

            }

        }

    }

    LL condMax(LL t) {

        LL ret = t;

        for (int i = maxl; i >= 0; --i) {

            if (!(a[i] >> i & 1)) continue;

            if (ret >> i & 1) continue;

            ret ^= a[i];

        }

        return ret;

    }

};

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    tot = 0; memset(ne, -1, sizeof ne);

    for (int i = 0; i < m; ++i) {

        int u, v; LL d;

        scanf("%d%d%lld", &u, &v, &d);

        add(u, v, d);

    }

    dfs(1, 0);

    LinearBasis lb;

    for (int i = 0; i < cnt; ++i) {

        if (b[i]) lb.insert(b[i]);

    }

    printf("%lld\n", lb.condMax(d[n]));

    return 0;

}