思路:

先搞出来所有的环的抑或值 随便求一条1~n的路径异或和

gauss消元找异或和最大 贪心取max即可

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 200050
#define int long long
int n,m,xx,yy,zz,w[N],v[N],next[N],first[N],tot,vis[N],d[N],stk[N],tp;
void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}
void add(int x,int y,int z){Add(xx,yy,zz),Add(yy,xx,zz);}
void dfs(int x){
vis[x]=1;
for(int i=first[x];~i;i=next[i]){
if(!vis[v[i]])d[v[i]]=d[x]^w[i],dfs(v[i]);
else if(d[v[i]]^d[x]^w[i])stk[++tp]=d[v[i]]^d[x]^w[i];
}
}
void gauss(){
for(int i=1ll<<62,flag=1,j;i;i>>=1){
for(j=flag;j<=tp;j++)if(stk[j]&i)break;
if(j==tp+1)continue;
swap(stk[flag],stk[j]);
for(int k=1;k<=tp;k++){
if(k==flag)continue;
if(stk[k]&i)stk[k]^=stk[flag];
}
flag++;
}
}
signed main(){
memset(first,-1,sizeof(first));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&xx,&yy,&zz);
add(xx,yy,zz);
}
dfs(1),gauss();
for(int i=1;i<=tp;i++)d[n]=max(d[n],d[n]^stk[i]);
printf("%lld\n",d[n]);
}

BZOJ 2115 DFS+高斯消元-LMLPHP

05-21 22:23