Problem

任意无向图上找到一条 1 到 n 的路径使得路上边权异或和最大。
可以重复走点或走边。

Solution

最近在搞线性基啊...
然后就做了这一道题，其实看了题解以后觉得不是很难打（

要点如下：

• 往回走无意义，因为边权会被异或抵消。
• 因此走向终点的路径绝对是一条路径 + 若干个环构成
• 因此只要预处理所有环的异或和丢到线性基里，求出任意一条路径的异或和在线性基上查询最大值就 OK 了。

原理如下：
对于一个环，它与路径有如下几种情况：

1. 路径被环包含。异或后则会切换到另一条路径。由于所有的环我们都已经处理了，所以求出任意一条的异或和是正确的。
2. 路径被环部分包含。异或后路径改变。 进一步包含了最优解。
3. 路径不与环相交。我们可以先走到那个环，然后走一圈再沿原路返回。是不是就把那个独立的环弄到手了？

然后这样子是保证得到最优解的，因此问题解决。

PS：对于找环，用深搜有一个比较巧妙的处理方式 orz...

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

const int N=5e4, M=2e5+10;
int h[N],to[M],nexp[M],p=1;
ll W[M];
inline void ins(int a,int b,ll w) {
    nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++;
}

template <typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

struct Basis {
    ll a[64];
    void insert(ll x) {
        for(int i=63;i>=0;i--)
            if(x&(1ll<<i)) {
                if(!a[i]) { a[i]=x; break; }
                x^=a[i];
            }
    }
    ll query(ll x=0) {
        for(int i=63;i>=0;i--)
            if(x<(x^a[i])) x^=a[i];
        return x;
    }
} ba;

ll tag[N];
ll path;
int n,m;
void dfs(int x) {
    for(int u=h[x];u;u=nexp[u]) {
        if(tag[to[u]]==-1) tag[to[u]]=tag[x]^W[u], dfs(to[u]);
        else ba.insert(tag[to[u]]^tag[x]^W[u]);
    }
}


int main() {
    gn(n), gn(m);
    ll w;
    for(int i=0,u,v;i<m;i++) gn(u), gn(v), gn(w), ins(u,v,w), ins(v,u,w);
    memset(tag,-1,sizeof(tag));
    tag[1]=0;
    dfs(1);
    printf("%lld\n",ba.query(tag[n]));
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4151.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆