【线性基】【洛谷P4151】[WC2011]最大XOR和路径

题目

https://www.luogu.com.cn/problem/P4151

思路

线性基神题

首先我们发现我们走出的路径去掉走两次的边之后一定是一条链和若干个环（要联通），并且对于一个环，我们可以选或者不选。容易想到线性基。

把所有的环DFS出来，丢进线性基里面，那么最后查询以这条链为基础查询就行。

现在的问题是怎么找出那条链？其实随便找一条就行
证明：如果A比B优，我们选了B，那么A和B一定构成一个环。只要BxorAB就变成A啦

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+77;
int cnt,ls[N],n,m;
ll p[65],d[N];
bool vis[N];
struct E
{
	int to,next; ll w;
}e[N<<1];
void add(int u,int v,ll w)
{
	e[++cnt].to=v; e[cnt].next=ls[u]; ls[u]=cnt; e[cnt].w=w;
}
void ins(ll x)
{
    for(int i=61; i>=0; i--) if((x>>i)&1)
    {
        if(!p[i])
        {
            p[i]=x; break;
        }
        else x^=p[i];
    }
}
void dfs(int u,ll yjy)
{
	vis[u]=1; d[u]=yjy;
	for(int i=ls[u]; i; i=e[i].next)
	{
		int v=e[i].to;
		if(!vis[v]) dfs(v,yjy^e[i].w);
		else ins(yjy^d[v]^e[i].w);
	}
}
ll query(ll x)
{
	ll yjy=x;
	for(int i=61; i>=0; i--) if((yjy^p[i])>yjy) yjy^=p[i];
	return yjy;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(ll i=1,x,y,w; i<=m; i++) scanf("%lld%lld%lld",&x,&y,&w),add(x,y,w),add(y,x,w);
	dfs(1,0);
	printf("%lld",query(d[n]));
}

最后

以上就是从容帅哥为你收集整理的【线性基】【洛谷P4151】[WC2011]最大XOR和路径的全部内容，希望文章能够帮你解决【线性基】【洛谷P4151】[WC2011]最大XOR和路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。