[bzoj2115]-[WC2011]最大XOR和路径

题目（BZOJ）
题目（洛谷）
 
如果你多造点小样例就会发现这题符合条件的一条路径是一堆环加一堆点，
故我们只需要先任意取一条路径求个初始ans，再对所有的环求个线性基，最后再求个最大值即可。
why？
因为最优路径和一开始任意选的路径一定构成一个环，ans异或上这个环等于选另一条路径。这是因为我们将这个环看成一个全集S，S中包含两条路径，一条路径xor上S得到S的补集。
完毕。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=50050;
int n,m,cnt;
ll ans,cir[N<<2],dis[N],ji[70];
bool vis[N];
struct edge{
	int vk;ll wk;int nxt;
}e[N<<2];
int head[N],tt;
inline void ad(int u,int v,ll w){e[++tt].vk=v;e[tt].wk=w;e[tt].nxt=head[u];head[u]=tt;}
void dfs(int u,int fa){
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].vk;
		if(v==fa)continue;
		if(!vis[v]){
			dis[v]=(dis[u]^e[i].wk);
			dfs(v,u);
		}
		else cir[++cnt]=(dis[u]^dis[v]^e[i].wk);
	}
}
int main(){
	read(n),read(m);
	for(int i=1;i<=m;++i){
		int u,v;ll w;
		read(u),read(v),read(w);
		ad(u,v,w),ad(v,u,w);
	}
	dfs(1,0);
	ans^=dis[n];
	for(int i=1;i<=cnt;++i){
		ll tmp=cir[i];
		for(int j=62;j>=0;--j){
			if(!(tmp>>j))continue;
			if(!ji[j]){ji[j]=tmp;break;}
			tmp^=ji[j];
		}
	}
	for(int i=62;i>=0;--i)ans=max(ans,(ans^ji[i]));
	printf(
	return 0;
}