BZOJ 2115 [WC2011] Xor

题目链接：传送门

o头像上被放了个小猪好Q
咕咕咕
感觉是一种板子
路径最大异或和
既然是异或
重复走一条路径是不会对答案有影响的
因为抵消掉了
所以我们考虑走图中的环
把图中环对答案的贡献加到线性基里去
再所以我们先从1随便走到n
然后考虑环
然后
然后然后线性基取最大值就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010

using namespace std;
typedef long long ll;
bool vis[A];
int head[A], num, a, b, n, m;
ll dis[A], p[61], c;
struct node {
    int next, to;
    ll dis;
}e[A];
void add(int fr, int to, ll dis) {
    e[++num].next = head[fr];
    e[num].dis = dis;
    e[num].to = to;
    head[fr] = num;
}
void insert(ll x) {
    for (int i = 60; i >= 0; i--)
        if (x & (1LL << i)) {
            if (!p[i]) {p[i] = x; break;}
            else x ^= p[i];
        }
}
void dfs(int fr) {
    vis[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next){
        int ca = e[i].to;
        if (!vis[ca]) {
            dis[ca] = dis[fr] ^ e[i].dis;
            dfs(ca);
        }
        else insert(dis[ca] ^ dis[fr] ^ e[i].dis);
    }
}
int main(int argc, char const *argv[]) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%lld", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dfs(1);
    for (int i = 60; i >= 0; i--)
        if ((dis[n] ^ p[i]) > dis[n])
            dis[n] ^= p[i];
    printf("%lld", dis[n]);
    return 0;
}