题意：在没有自环的连通图中找一条回路，使路径上所有边权xor值最大(同一条路走过多次需要重复计算)
2<=N<=50000；1<=M<=100000;0<=wi<=260-1.1~30组数据，4000MS
xor高斯消元：在图中寻找环，并计算找到的环的总xor值(每条边、每个点都只用走一次，显然没找出来的环可以用找到的所有环的xor值的子集的xor值结果表示)，显然每条回路答案都可以用这些所有环的xor值的子集的xor值结果表示，则对所有环的xor值进行xor高斯消元。
说起这个xor高斯消元就厉害了，可用于计算一个数集所有子集的数的xor值的最大值：将所有数拆分成二进制形式，列出xor方程组——对每一个二进制位都列出一个方程组，右边常数项为1，从高位向低位判断是否相容，相容则该位可以为1，不相容则将这条方程删去，该位为0。
具体来说，以a[i][j]表示第j个数的第i个二进制位，从上至下，在每行寻找不为0的系数，若有，则该方程满足条件，同时消去下面方程的该变元(某条方程该处系数为1，则对这条方程进行xor消元)，若没有，但常数项为0，方程亦满足条件，常数项为1则不满足条件，满足条件则ans+=1ll<<i；由于我们从高位向低位做，不满足条件则抽去该方程，所以能保证xor值最大(贪心思想)，复杂度O(环*环*61)
#include<cstdio> #include<cstring> #include<vector> #include<iostream> using namespace std; const int maxm=200000; const int maxn=100000; int t,u,v,n,m,sb,tot; long long x,y,w,tmp; long long ans; int head[maxn]; long long edge[2*maxm][3]; bool ve[2*maxm]; vector<long long> huan; bool vis[maxn]; int gs[70][maxn]; long long cf[maxn]; void add_edge(int x,int y,long long w){ edge[++tot][0]=y;edge[tot][1]=w;edge[tot][2]=head[x];head[x]=tot; edge[++tot][0]=x;edge[tot][1]=w;edge[tot][2]=head[y];head[y]=tot; } void dfs(int fa,int v,long long xo){ cf[v]=xo;vis[v]=true; for (int i=head[v];i;i=edge[i][2]) if (edge[i][0]!=fa && !ve[i]) { ve[i]=true;ve[i^1]=true; if (vis[edge[i][0]]) huan.push_back(xo^cf[edge[i][0]]^edge[i][1]); else dfs(v,edge[i][0],xo^edge[i][1]); } } void gauss(){ bool flag; for (int i=1;i<=61;++i){ flag=false; for (int j=1;j<=sb;++j) if (gs[i][j]) { ans+=1ll<<(61-i); for (int k=i+1;k<=61;++k) if (gs[k][j]) for (int l=1;l<=sb+1;++l) gs[k][l]^=gs[i][l]; flag=true;break; } if (!flag && gs[i][sb+1]==0) {ans+=1ll<<(61-i);} } } int main(){ scanf("%d",&t); for (int q=1;q<=t;++q){ scanf("%d%d",&n,&m); memset(ve,false,sizeof(ve));memset(head,0,sizeof(head)); tot=-1; huan.clear(); for (int i=1;i<=m;++i){ scanf("%d%d%lld",&u,&v,&w); add_edge(u,v,w); } memset(vis,false,sizeof(vis)); dfs(-1,1,0);memset(gs,0,sizeof(gs));sb=huan.size(); for (int i=0;i<sb;i++){ x=huan[i]; for (int j=60;j>=0;--j) if (x & 1ll<<(j)){ gs[61-j][i+1]=1; } } for (int i=0;i<=61;++i) gs[i][sb+1]=1; ans=0; gauss(); printf("Case #%d: %lld ",q,ans); } return 0; }