[题解]BZOJ2115 XOR

传

参

Description

Input

第一行包含两个整数N和 M，表示该无向图中点的数目与边的数目。接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在一条权值为 Di的无向边。图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

Sample Input

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

HINT

分析

以1为根建DFS树。

先随便找一条从1到n的路记异或和为(W)，再记录每一个环的权值，最后的答案就是(W)异或这些环的任意一个子集得到的最大值。

证明：

首先，容易发现最后的答案就是一条从1到n的路径加上若干个环：

假设这个环和一开始选择的那条路没有公共点，那么可以从1走到环上的某一个点(u)，然后遍历整个环再从(u)回到1，那么由于1到(u)的路走了两次，所以没有贡献，贡献就是这个环的价值。

如果环和路径有公共点，那么显然。

然后证明为什么一开始随便选一条路径是对的：

假设有一条从1到n的更优的路径，那么在找环的时候一定可以找到由它和原来那条路径构成的一个环，异或一下之后就可以看成一开始就选择了更优的那一条。

然后线性基维护一下就可以了

代码

#include<bits/stdc++.h>
#define rep(X,A,B) for(int X=A;X<=B;X++)
#define tep(X,A,B) for(int X=A;X>=B;X--)
#define LL long long
const int N=50010;
const int M=200010;
using namespace std;

int n,m,maxn=0;
LL val[M],vis[210],hlp[N],ans=-1;
int com[N],edge[M],lst[N],nxt[M],t=0;

void ADD(int x,int y,LL z){
	edge[++t]=y;nxt[t]=lst[x];lst[x]=t;val[t]=z;
}

void READ(){
	int u,v;LL w;
	scanf("%d%d",&n,&m);
	rep(i,1,n)com[i]=0;
	rep(i,1,m){
		scanf("%d%d%lld",&u,&v,&w);
		ADD(u,v,w);ADD(v,u,w);
	}
}

void BUILD(LL x){
	if(!x)return;
	int pos=0;LL now=x;
	while(x)pos++,x/=2;
	maxn=max(maxn,pos);
	tep(i,pos,1){
		if(!(now>>(i-1)))continue;
		if(!vis[i]){
			vis[i]=now;
			return;
		}
		now^=vis[i];
	}
}

void SEARCH(int x,LL num){
	com[x]=1;
	hlp[x]=num;
	for(int r=lst[x];r;r=nxt[r]){
		if(com[edge[r]]==1)BUILD(num^val[r]^hlp[edge[r]]);
		if(com[edge[r]]==0)SEARCH(edge[r],num^val[r]);
	}
	com[x]=-1;
}

void GET(){
	ans=hlp[n];
	tep(i,maxn,1)ans=max(ans,ans^vis[i]);
	printf("%lld
",ans);
}

int main(){
	READ();
	SEARCH(1,0);
	GET();
	return 0;
}