Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门

考虑最终的答案一定是一条1->n的链和若干个环组成。

所以预处理出所有环的Xor放入线性基中。

考虑下面两种情况:

对答案有贡献的环需要从路径上走过去再走回来,那么过程中的影响会因为来回走而抵消。

度过存在另一条更优秀的1->n的路径,那么这条路径和我们随意选择的路径构成了环,那么它一定会被放在线性基内。

#include <cstdio>
using namespace std;

typedef long long LL;
const int Maxn=1e5+5;

LL B[65];

void Ins(LL x){
    for(int j=63;~j;j--){
        if((x>>j)&1){
            if(!B[j]){B[j]=x;break;}
            x^=B[j];
        }
    }
}
LL Qur(LL x){
    for(int j=63;~j;j--){
        if((x^B[j])>x)x^=B[j];
    }return x;
}

LL w[Maxn<<1],c,dis[Maxn];
int N,M,vis[Maxn];
int head[Maxn],nxt[Maxn<<1],to[Maxn<<1],Cnt,x,y;
#define Add(x,y,c) (nxt[++Cnt]=head[x],to[head[x]=Cnt]=y,w[Cnt]=c)

void dfs(int x,LL res){
    dis[x]=res,vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
        if(vis[to[i]])Ins(dis[x]^dis[to[i]]^w[i]);
        else dfs(to[i],res^w[i]);
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        scanf("%d%d%lld",&x,&y,&c);
        Add(x,y,c),Add(y,x,c);
    }
    dfs(1,0),printf("%lld\n",Qur(dis[N]));
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*