题解 | xor 题解

首先有个显然的结论：图中所有环的xor和都可以取到（考虑从1走过去绕一圈回来，那么过去那段路的xor和就抵消了），dfs处理出所有的环（这个可以通过记录in_edge然后利用返祖边找环，在搜索树上维护前缀和即可），扔进线性基中，然后随便选一条1到n的路径，在线性基取max即可。
考虑证明正确性：
如果从1到n有多条路径，那么显然路径处于多个环上，假设现在有两条路，1->2->4,1->3->4,如果选了1->2->4，但是1->3->4更优，那么在线性基中就会选出1-2-3-4这个环，然后xor上后就变成了取了1->3->4这条路径，所以这么做是正确的（最后xor出来的路径一定会是最优的那条路径）

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 200010;

bool vis[N];
ll s[N];
int cnt = 1, head[N], n, m;
struct edge {int to, nxt; ll v;} e[N<<1];
struct lb {
    ll p[64];
    void insert(ll x) {
        for(ll i = 63; i >= 0; --i) {
            if((x >> i) & 1LL) {
                if(p[i]) x ^= p[i];
                else {p[i] = x; break;}
            }
        }
    }
    ll query(ll ans) {
        for(ll i = 63; i >= 0; --i) {
            if((ans ^ p[i]) > ans) ans ^= p[i];
        }
        return ans;
    }
} B;

void ins(int u, int v, ll w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}

void dfs(int u, int in_edge) {
    vis[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if((i ^ 1) == in_edge || i == in_edge) continue;
        if(vis[v]) {
            B.insert(s[u] ^ s[v] ^ e[i].v);
            continue;
        }
        s[v] = s[u] ^ e[i].v;
        dfs(v, i);
    }
}

int main() {
    scanf("%d%d", &n, &m); ll w;
    for(int u, v, i = 1; i <= m; ++i) {
        scanf("%d%d%lld", &u, &v, &w);
        ins(u, v, w), ins(v, u, w);
    }
    dfs(1, -1);
    printf("%lld\n", B.query(s[n]));
}