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

· · 题解

一道线性基+图论的板子题

我们假设dis_i表示1\to i的简单路径的异或和

如果路径上的各顶点均不互相重复，称这样的路径为简单路径。

我们来考虑一下没有环的情况

很显然，此时的答案为dis_n这不废话吗

但如果有环呢？

此时有两种情况：

  1. 不经过这个环
  2. 经过这个环

对于情况1，显然此时的值为dis_n

对于情况2，经过观察我们发现：

Ans=dis_n\oplus k\oplus c\oplus k=dis_n\oplus c

如果有3个环呢

经过这三个环的答案即为

Ans=dis_n\oplus c_1\oplus c_2\oplus c_3

因此我们得出结论:答案可以由一条1\to n的路径异或若干个环得到

那么问题由来了：如果从1\to n有多条路径呢？

很显然，

\color{red}\text{红色的链}\color{black}\oplus \color{green}\text{绿色的链}\color{black}=\color{orange}\text{黄色的环} \color{red}\text{红色的链}\color{black}\oplus \color{orange}\text{黄色的环}\color{black}=\color{green}\text{绿色的链}

因此我们可以取任意一条链，通过异或环得到所有情况

于是我们把问题转换成了两个子问题：

对于问题一，随便搞一个dfs就过了

问题二不会的话为什么来做这道题出门左转【模板】线性基谢谢

接下来我们就可以愉快地敲出正解了

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;char c=getchar();bool f=false;
    for(;!isdigit(c);c=getchar())f!=c=='-';
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    if(f)x=-x;
}
template<typename T ,typename ...Arg>
inline void read(T &x,Arg &...args){
    read(x);read(args...);
}
template<typename T>
inline void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
typedef long long ll;
const ll maxn=50000+100;
const ll maxm=100000+100;
bool flag[maxn];
ll dis[maxn];
const ll maxn_wei=64;
struct XXJ{
    //线性基板子
    ll b[maxn_wei];
    void init(){memset(b,0,sizeof b);}
    void insert(ll x){
        for(ll i=maxn_wei-1;i>=0;i--){
            if(!(x&(1ll<<i)))continue;
            if(!b[i]){
                b[i]=x;
                return ;
            }
            x^=b[i];
        }
    }
}Base;
struct Graph{
    struct Edge{ll v,w,nxt;}e[maxm*2];
    ll cnt,head[maxn];
    void init(){memset(head,0,sizeof head);cnt=0;}
    void add(ll u,ll v,ll w){e[++cnt]=(Edge){v,w,head[u]};head[u]=cnt;}
    #define For(G,i) for(ll eee=(G).head[(i)];eee;eee=(G).e[eee].nxt)
    #define v(G) (G).e[eee].v
    #define w(G) (G).e[eee].w
}G;
void dfs(ll x,ll res){
    dis[x]=res;
    flag[x]=true;
    For(G,x){
        if(!flag[v(G)])dfs(v(G),res^w(G));
        else Base.insert(res^w(G)^dis[v(G)]);
    } 
}
ll n,m,u,v,w;
signed main(){
    read(n,m);
    for(ll i=1;i<=m;i++){
        read(u,v,w);
        G.add(u,v,w);
        G.add(v,u,w);
    }
    dfs(1,0);
    ll ans=dis[n];
    for(ll i=maxn_wei-1;i>=0;i--)
        if((ans^Base.b[i])>ans)
            ans^=Base.b[i];
    write(ans);
}