[WC2011]最大XOR和路径

LG传送门

需要充分发掘经过路径的性质：首先注意不一定是简单路径，但由于统计的是异或值，重复走是不会被统计到的，考虑对于任意一条从\(1\)到\(n\)的路径的有效部分是什么。最简单的情况就是走一条链，有时候我们会从这条链走出去，走一段路径之后走一个环，再沿这条路径回到原来的链上，这样一来答案就变成了原来的链异或找到的环。我们发现任意的环都可以用来更新答案，那么我们找到原图中所有的环丢进线性基里，再把所有一条\(1\)到\(n\)的链在线性基里查询最大异或和就行了。但事实上最后一步我们只要用任意一条\(1\)到\(n\)的链来查询。

你可能会对于我们任意找的一条链的最优性有疑问，事实上原图上\(1\)到\(n\)之间的所有链都可以通过其中的任意一条异或某一个环得到，所以事实上我们还是找出了所有的链。

//written by newbiechd

#include <cstdio>

#include <cctype>

#define R register

#define I inline

#define B 1000000

#define L long long

using namespace std;

const int N = 50003, M = 200003, S = 64;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I L rd() {

    R L f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int vis[N], h[N], E;

L val[N], base[S];

struct edge {

    int g, s;

    L w;

}e[M];

I L max(L x, L y) { return x > y ? x : y; }

I void add(int x, int y, L z) { e[++E] = (edge){y, h[x], z}, h[x] = E; }

I void insert(L x) {

    for (R int i = S - 1; ~i; --i)

        if ((x >> i) & 1) {

            if (!base[i])

                base[i] = x;

            x ^= base[i];

        }

}

I L query(L x) {

    for (R int i = S - 1; ~i; --i)

        x = max(x, x ^ base[i]);

    return x;

}

void dfs(int x) {

    for (R int i = h[x], y; i; i = e[i].s)

        if (!vis[y = e[i].g])

            vis[y] = 1, val[y] = val[x] ^ e[i].w, dfs(y);

        else

            insert(val[y] ^ val[x] ^ e[i].w);

}

int main() {

    R int n = rd(), m = rd(), i, x, y;

    L z;

    for (i = 1; i <= m; ++i)

        x = rd(), y = rd(), z = rd(), add(x, y, z), add(y, x, z);

    vis[1] = 1, dfs(1), printf("%lld", query(val[n]));

    return 0;

}

巴特西

[WC2011]最大XOR和路径线性基

[WC2011]最大XOR和路径

最新文章

热门文章

巴特西

[WC2011]最大XOR和路径 线性基

[WC2011]最大XOR和路径

最新文章

热门文章

[WC2011]最大XOR和路径线性基