BZOJ 2115 Wc2011 Xor DFS+高斯消元

BZOJ 2115 Wc2011 Xor DFS+高斯消元

題目大意：給定一個無向圖，每條邊上有邊權，求一條1到n的路徑，使路徑上權值異或和最大

首先一條路徑的異或和可以化為一條1到n的簡單路徑和一些簡單環的異或和

我們首先DFS求出任意一條1到n的簡單路徑以及圖中所有最簡單的簡單環(環上不存在兩個點可以通過環外邊直連)

然後在一些數中選出一個子集，使它們與一個給定的數的異或和最大，這就是高斯消元的問題了

利用高斯消元使每一位只存在於最多一個數上 然後貪心求解即可

#include
#include
#include
#include
#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<