「Bzoj 2115」「Wc2011」Xor (线性基 + DFS)

Bzoj 2115
题意：给定一张无向图带边权图，求图上一条$1 \rightarrow n$路径的异或和最大值。

路径不要求简单路径，那么这个路径就是一条链+一些环
我们随便找一条$1 \rightarrow n$的链，然后考虑在其中加上环
如果环和链有交，那么直接异或环的异或和是对的
如果没有交，我们要走过去再走回来，连接路径抵消了，也是对的

为什么我们可以随便选链呢，因为$1 \rightarrow n$的任意两条链一定可以构成环然后就是上面的问题

所以我们随便选个链，再把所有环的异或和丢进线性基

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 50000 + 5;

    int vis[MAXN], n, m;
    LL dis[MAXN], a[105];
    vector<int > G[MAXN];
    vector<LL > val[MAXN];

    void ins(LL t) {
        if (t) for (LL i = 63; ~i; --i) {
            if (!((t >> i) & 1ll)) continue ;
            if (a[i]) t ^= a[i]; else {
                for (LL j = 0; j < i; ++j) if ((t >> j) & 1ll) t ^= a[j];
                for (LL j = i + 1; j <= 63; ++j) if ((a[j] >> i) & 1ll) a[j] ^= t;
                a[i] = t;
                break ;
            }
        }
    }

    void dfs(int u, LL D) {
        dis[u] = D;
        vis[u] = 1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            LL w = val[u][i];
            if (dis[v] >= 0) ins(dis[v] ^ w ^ dis[u]);
            if (!vis[v]) dfs(v, D ^ w); 
        }
    }

    void clean() {
        ms(dis, -1);
    }
    int solve() {

        clean();
        cin >> n >> m;
        LL w;
        for (int x, y, i = 1; i <= m; ++i) {
            scanf("%d%d%lld", &x, &y, &w);
            G[x].push_back(y), val[x].push_back(w);
            G[y].push_back(x), val[y].push_back(w);
        }
        dfs(1, 0);
        LL ans = dis[n];
        for (int i = 0; i <= 63; ++i) if ((ans ^ a[i]) > ans) ans ^= a[i];
        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
*/