zcmimi's blog
avatar
zc
2020-06-04 12:21:00
  • 本文总阅读量
查看原题

点击跳转

[WC2011]最大XOR和路径

#include<bits/stdc++.h>
int rd(){int x=0;char c;bool f=0;for(c=getchar();c<'0'||'9'<c;c=getchar())f^=c=='-';for(x=c-48,c=getchar();'0'<=c&&c<='9';x=x*10+c-48,c=getchar());return f?-x:x;}
const int N=100011;
int n,m,cnt,head[N],d[N],p[30];
struct edge{int to,nxt,w;}e[N<<1];
void add(int x,int y,int w){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].w=w;}
void ins(int x){
    for(int i=27;x,~i;--i)if(x>>i){
        if(!p[i]){p[i]=x;return;}
        x^=p[i];
    }
}
bool v[N];
void dfs(int x){
    v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!v[to])d[to]=d[x]^e[i].w,dfs(to);
        else ins(d[x]^d[to]^e[i].w);
}
int main(){
    n=rd(),m=rd();
    int x,y,w;
    while(m--)
        x=rd(),y=rd(),w=rd(),
        add(x,y,w),add(y,x,w);
    dfs(1);x=d[n];
    for(int i=27;~i;--i)
        if((x^p[i])<x)x^=p[i];
    printf("%d\n",x);
}
LG CF845G Shortest Path Problem
comment评论
Search
search