[luogu] P4151 [WC2011]最大XOR和路径 dfs+线性基

前言

传送门 :

题意

给你一个无向有权图(含环),求一条从 1 − N 1 - N 1−N的路径上,异或和最大

思路

这道题,虽然看完题解之后感觉异常简单,但是撸起来还是非常困难的

首先 : 如果没有环,那么只需要求 v [ 1 ] x o r . . . . . v [ N ] v[1] xor.....v[N] v[1]xor.....v[N]即可

但是因为有环的参与,导致答案会被环更新,由于到环的距离来回一次所以不考虑

因此答案最后是 v [ 1 ] x o r . . . v [ N ] v[1] xor ...v[N] v[1]xor...v[N]

但是可能存在多条直达 1 − N 1-N 1−N的路径,但是因为无向图,多条路径可看成一个环,因此不考虑

所以最后我们只需要求 一条路径 xor 多个环 m a x max max

前者可以使用 d f s dfs dfs求出,后者使用 线性基 即可

参考 : 博文链接

虽然简单,但是 d e b u g debug debug半小时之久 第一 : 没看 M M M的范围,导致 R E RE RE 第二 : 没开 L L LL LL 第三 : 异或优先级低于 > > >

Mycode

#define int long long
const int N  = 1e5+100;
struct node{
	int to,val;
};
vector g[N];

ll st[N],dist[N];
ll p[N];

int h[N*2],e[N*2],ne[N*2],w[N*2],idx;
void add(int a,int b,int c){
	e[++idx] =  b , ne[idx] = h[a] , w[idx] = c,h[a] = idx;
}
void xor_insert(ll x){
	for(int i = 63 ; i>= 0 ; i -- ){
		if(!(x >>(ll)i)){
			continue;
		}
		if(!p[i]){
			p[i] = x;
			break;
		}
		x ^= p[i];
	}
}

void dfs(int u,ll val){
	dist[u] = val;
	st[u] = 1;
	for(int i =h[u];i;i=ne[i]){
		int j = e[i];
	
		
		if(!st[j]) dfs(j,val^w[i]);
		else xor_insert(val^dist[j]^w[i]);
	}
	// for(auto x : g[u]){
		// if(!st[x.to]) dfs(x.to,val^x.val);
		// else xor_insert(val^dist[x.to]^x.val);
	// }
}
void solve()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i>a>>b>>c;
		// g[a].pb({b,c});
		// g[b].pb({a,c});
		add(a,b,c);add(b,a,c);
		
	}

	dfs(1,0);
	ll ans =  dist[n];

	
	for(int i =63;i>=0;i -- ){
		if( (ans ^p[i]) > ans)
		ans^=p[i];
	}

	cout