洛谷P4151 最大XOR和路径 [WC2011] 线性基+图论

正解:线性基+图论

解题报告:

传送门

首先可以思考一下有意义的路径会是什么样子,,,那就一定是一条链+一些环

挺显然的因为一条路径原路返回有没有意义辣?所以一定是走一条链+一些环(当然也可以麻油环,,,差不多差不多QAQ

所以可以考虑先把所有环找出来,加入线性基中,现在要考虑的就只有找一条链这个事儿辣

然后这儿可以发现一个性质,就是其实只要拿1号节点到n号节点的任意一条链出来就欧克了,显然的是所有1到n的路径都能通过异或若干个环得到,好像挺显然的,意会下趴QAQ

然后找环什么的还挺简单的,,,dfs一下找到返祖边就加入线性基就好QAQ

over,感觉最近博客越来越短辣QAQ

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define ll long long

#define int long long

#define gc getchar()

#define mp make_pair

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ll i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,M=+;

int n,m,poww[]={},val[N<<],ed_cnt,head[N<<];

bool vis[N];

struct ed{int to,nxt,wei;}edge[M<<];

struct xxj

{

    ll a[];int num_cnt;

    il void clr(){memset(a,,sizeof(a));num_cnt=;}

    il void insert(ll x){if(num_cnt==)return;my(i,,)if(x&poww[i]){x^=a[i];if(!a[i]){a[i]=x,++num_cnt;return;}}}

    il ll mx(ll ret){my(i,,)ret=max(ret,ret^a[i]);return ret;}

}gdgs;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch<'' || ch>''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri x,ri y,ri z){edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],z};head[x]=ed_cnt;}

void dfs(ri x,ri fa)

{vis[x]=;e(i,x)if(t(i)^fa)if(!vis[t(i)])val[t(i)]=val[x]^w(i),dfs(t(i),x);else gdgs.insert(val[x]^val[t(i)]^w(i));}

main()

{

//    freopen(".in","r",stdin);freopen(".out","w",stdout);

    rp(i,,)poww[i]=poww[i-]<<;

    n=read();m=read();rp(i,,m){ri x=read(),y=read(),z=read();ad(x,y,z);ad(y,x,z);}

    dfs(,);printf("%lld\n",gdgs.mx(val[n]));

    return ;

}

//有个要注意的点,,,虽然我不知道为什么QAQ

//就空间要开两倍,,,不知道为什么但我开始都开的一半然后RE了三个点,,,我就偷懒都开了两倍QAQ

放下代码QAQ