题目地址：洛谷：【P4151】[WC2011]最大XOR和路径 – 洛谷、BZOJ：Problem 2115. — [Wc2011] Xor

题目描述

题意简述

给你一个n点m边的无向图，求一条1到n的路径使边权异或和最大。

输入输出格式

输入格式：
第一行包含两个整数 N 和 M， 表示该无向图中点的数目与边的数目。
接下来 M 行描述 M 条边，每行三个整数Si，Ti，Di，表示 Si 与 Ti 之间存在一条权值为 Di 的无向边。
图中可能有重边或自环。

输出格式：
仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

输入输出样例

输入样例#1：

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2 

输出样例#1：

6

说明

题解

首先，我们考虑异或和最大的路径应该是怎么样的。我们考虑图中的环，显然我们可以从任意一个节点走到环上，绕环一圈，再走回来，这样只有这个环的权值异或和就被异或了进去。那么我们可以DFS处理一遍环的权值异或和来得到一个集合。
具体来说，DFS如果遇到一条边两端的点都已经访问过，那么就可以将dis[u]^dis[v]^边权记作环的权值异或和，这是由于dis[u]^dis[v]会将不在环上的边通过一次异或消去。
我们发现，我们只需要用一条1到n的路径再组合上这个集合的某一些权值使得异或和最大就行了。对于这个集合的处理，我们可以求线性基，这样就可以代表所有可能的情况的异或值。我们只需要任选一条1到n的路径并且使用线性基计算最大值就可以了。
任选一条路径为什么是正确的？我们考虑1到n的路径假如有2条，那么这两条路径会构成环，任选其中一条，再异或上这个环，实际上得到了另一条路径的异或和，而环的情况刚刚已经处理过，我们可以保证答案最优。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005;

int n, m;

struct Edge {
    int to;
    LL w;
};

std::vector<Edge> gra[MAXN];

bool vis[MAXN];
LL dis[MAXN];
std::vector<LL> cir;

inline void dfs(int u) {
    vis[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(vis[v]) {
            cir.push_back(dis[v] ^ dis[u] ^ gra[u][i].w);
        } else {
            dis[v] = dis[u] ^ gra[u][i].w;
            dfs(v);
        }
    }
}

LL mat[65];

int main() {
    n = readint(); m = readint();
    int u, v; LL w;
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u].push_back(Edge {v, w});
        gra[v].push_back(Edge {u, w});
    }
    dfs(1);
    for(int i = 0; i < cir.size(); i++) {
        for(int j = 63; j >= 0; j--) {
            if(cir[i] & (1ll << j)) { // 这里不是1ll会爆int
                if(!mat[j]) {
                    mat[j] = cir[i];
                    break;
                } else {
                    cir[i] ^= mat[j];
                }
            }
        }
    }
    LL ans = dis[n];
    for(int i = 63; i >= 0; i--) {
        ans = std::max(ans, ans ^ mat[i]);
    }
    printf("%lld", ans);
    return 0;
}