BZOJ 2115 Wc2011 Xor DFS+高斯消元

标题效果：鉴于无向图。右侧的每个边缘，求一个1至n路径，右上路径值XOR和最大

首先，一个XOR并能为一个路径1至n简单的路径和一些简单的XOR和环

我们开始DFS获得随机的1至n简单的路径和绘图环所有线性无关(两个或多个环异或得到)

然后在一些数中选出一个子集。使它们与一个给定的数的异或和最大，这就是高斯消元的问题了

利用高斯消元使每一位仅仅存在于最多一个数上然后贪心求解就可以

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 50500

using namespace std;

typedef long long ll;

struct abcd{

	int to,next;

	ll f;

}table[200200];

int head[M],tot;

int n,m,top;

bool v[M];

ll _xor[M],stack[M<<2],ans;

void Add(int x,int y,ll z)

{

	table[++tot].to=y;

	table[tot].f=z;

	table[tot].next=head[x];

	head[x]=tot;

}

void DFS(int x)

{

	int i;

	v[x]=true;

	for(i=head[x];i;i=table[i].next)

	{

		if(v[table[i].to])

			stack[++top]=_xor[x]^table[i].f^_xor[table[i].to];

		else

			_xor[table[i].to]=_xor[x]^table[i].f,DFS(table[i].to);

	}

}

void Gaussian_Elimination()

{

	int i,k=0;

	ll j;

	for(j=1ll<<62;j;j>>=1)

	{

		for(i=k+1;i<=top;i++)

			if(stack[i]&j)

				break;

		if(i==top+1)

			continue;

		swap(stack[++k],stack[i]);

		for(i=1;i<=top;i++)

			if( (stack[i]&j) && i!=k )

				stack[i]^=stack[k];

	}

}

int main()

{

	int i,x,y;

	ll z;

	cin>>n>>m;

	for(i=1;i<=m;i++)

	{

		scanf("%d%d%lld",&x,&y,&z);

		Add(x,y,z);

		Add(y,x,z);

	}

	DFS(1);

	Gaussian_Elimination();

	ans=_xor[n];

	for(i=1;stack[i];i++)

		if( (ans^stack[i])>ans )

			ans^=stack[i];

	cout<<ans<<endl;

}

//lld!!!!

秒客网

BZOJ 2115 Wc2011 Xor DFS+高斯消元

相关文章