题解 P4151 【[WC2011]最大XOR和路径】

· · 题解

线性基小结(估计来写WC的也没有需要看这个的了555。。。)
原题传送门
看见异或最值，估计线性基跑不了了。
考虑先随便提出一条从1到n的路径，这显然不一定是最优的，但是可以让它变强。比如可以让它中间插入一个环来让它变优。比如说有一条路径:

$1->A->B->E->F->G->E->B->C->N

注意到权值的变化其实就是多异或了那个环上的异或和，然后一个线性基的模型就出来了。把所有的环丢到线性基里面去，然后和我们选出的这条路径异或取个最大值就可以了。但是有没有可能我们最先选出的路径限制了我们的答案，而选另一条路径更优呢？假设存在一条路径:1->A->N,另一条路径为1->B->N,那1->A->N->B->1就形成了一个环，前面那条路径异或这个环就变成了后者，反之亦然。于是正确性就保证了。

#include <cstdio>
using namespace std;
#define R register
#define LL long long
const int MAXN=5e4+10;
const int MAXM=2e5+10;
const int MB=63;
int n,m;
struct Edge { int to,next; LL w; } e[MAXM];
int head[MAXN],cnt;
inline void add(int x,int y,LL w) {
    e[++cnt]={y,head[x],w}; head[x]=cnt;
}
LL p[MB+1];
inline void ins(LL x) {
    for(R int i=MB;i>=0;i--)
        if(x&(1LL<<i)) {
            if(!p[i]) { p[i]=x; return ;}
            else x^=p[i];
        }
}
inline LL ask(LL x) {
    for(R int i=MB;i>=0;i--)
        if((x^p[i])>x) x^=p[i];
    return x;
}
int vis[MAXN];
LL res[MAXN];
inline void dfs(int x,int fr,LL v) {
    vis[x]=1; res[x]=v;
    for(R int i=head[x];i;i=e[i].next) {
        int y=e[i].to;
        if(y==fr) continue;
        if(vis[y]) ins(res[y]^res[x]^e[i].w);
        else dfs(y,x,v^e[i].w);
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(R int i=1;i<=m;i++) {
        int x,y; LL z;
        scanf("%d%d%lld",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    dfs(1,0,0);
    printf("%lld\n",ask(res[n]));
    return 0;
}