zcmimi's blog
avatar
zc
2020-06-02 13:14:00
  • 本文总阅读量
查看原题

点击跳转

(以下长度定义为边权异或和)

首先钦定一条1到n的路径

容易发现可以通过环来增广路径

路径到环中间的路程要走两次,相当于没有

那么把所有环的长度插入线性基,

直接随意找一条1到n的路径,然后求这条路径长度在线性基上最大能异或成多少即可

假设1到n有一条更好的路径,那么会和刚才钦定的路径形成一个环,相当于异或时已经考虑过了

#include<bits/stdc++.h>
const int N=100001,inf=2122219134;
typedef long long ll;
int n,m,cnt,head[N];
struct edge{int to,nxt;ll w;}e[N<<1];
void add(int x,int y,ll w){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt;e[cnt].w=w;}
ll p[61],d[N],ans;
void ins(ll x){
    for(int i=60;~i;--i)if(x>>i){
        if(!p[i]){p[i]=x;return;}
        x^=p[i];
    }
}
ll ask(ll ans){
    for(int i=60;~i;--i)
        if((ans^p[i])>ans)ans^=p[i];
    return ans;
}
bool v[N];
void dfs(int x,ll res){
    d[x]=res,v[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
        if(v[e[i].to])ins(res^e[i].w^d[e[i].to]);
        else dfs(e[i].to,res^e[i].w);
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y;ll w;
    while(m--)
        scanf("%d%d%lld",&x,&y,&w),
        add(x,y,w),add(y,x,w);
    dfs(1,0);
    ans=d[n];
    for(int i=60;~i;--i)
        if((ans^p[i])>ans)ans^=p[i];
    printf("%lld\n",ans);
}
LG 4151 [WC2011]最大XOR和路径
comment评论
Search
search