洛谷P4151/WC2011 最大XOR和路径

@Pelom  November 5, 2019

题意

给出一张无向图,求$1 \rightarrow n$的最大异或和路径

数据范围:$n \le 50000,m \le 100000,d_i \le 10^{18}$

题解

考虑没有环的情况,答案为$dis[n]$
若存在环,由于从$1 \rightarrow n$的路径上到环上的路径需要走两遍(去/回),相当于没有计算
因此统计图上环的异或和,再与$dis[n]$异或求最大值
而多个值异或的最大值可用线性基求

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=50000+10;
const int L=60+5;
int n,m,u,v;
LL w;
int cnt;
int head[N];
LL dis[N];
bool vis[N];
struct edge{
    int nxt,to;
    LL w;
} e[N<<2];
struct basis{
    LL bas[L];
    inline void insert(LL x){
        for(int i=60;~i;i--){
            if(!(x>>i))
                continue;
            if(!bas[i]){
                bas[i]=x;
                break;
            }
            x^=bas[i];
        }
    }
    inline LL query(LL x){
        for(int i=60;~i;i--)
            x=max(x,x^bas[i]);
        return x;
    }
} b;
inline void add(int u,int v,LL w){
    e[++cnt]=(edge){head[u],v,w};
    head[u]=cnt;
}
void dfs(int u){
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]){
            b.insert(dis[u]^e[i].w^dis[v]);
            continue;
        }
        dis[v]=dis[u]^e[i].w;
        dfs(v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1);
    printf("%lld",b.query(dis[n]));
    return 0;
}

添加新评论