题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2115
思路很精妙。好像能应用到很多地方。
发现如果路径上有环，可以通过一些走法达到 异或了那个环 或 没有异或那个环。
所以路径上如果有环，可以把它们的异或值都存下来，之后随便挑选。
发现所有1~n的路径互相成环。
这样就能随便找一条路径，然后把所有环的异或值存下来，用高斯消元随便挑选。
消元的时候尽量保留高位，而且要上下消，这样保留下来的每一行的首位就不会被其他行的挑选情况影响。
注意挑选的时候是取max，不是 | 什么的。
1.找环，可以先弄个生成树，然后每条非树边成环。也可以在dfs里顺便判断。
2.左移是 1ll ！！！
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int N=5e4+5,M=1e5+5,LM=16; int n,m,head[N],xnt=1,tot,fa[N]; ll dis[N],ml,a[M]; bool vis[M<<1],/*vis[N],*/flag; struct Ed{ int next,fr,to;ll w; Ed(int n=0,int f=0,int t=0,ll w=0):next(n),fr(f),to(t),w(w) {} }ed[M<<1]; void add(int x,int y,ll z) { ed[++xnt]=Ed(head[x],x,y,z);head[x]=xnt; ed[++xnt]=Ed(head[y],y,x,z);head[y]=xnt; } int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);} void dfs(int cr,int f) { for(int i=head[cr],v;i;i=ed[i].next) if(vis[i]&&(v=ed[i].to)!=f) { dis[v]=(dis[cr]^ed[i].w); dfs(v,cr); } } void sc() { for(int i=1;i<=n;i++)fa[i]=i; int lm=(m<<1); for(int i=2;i<=lm;i+=2) if(find(ed[i].fr)!=find(ed[i].to)) { vis[i]=vis[i^1]=1;fa[find(ed[i].fr)]=find(ed[i].to); } dfs(1,0); for(int i=2;i<=lm;i+=2) if(!vis[i]) a[++tot]=(dis[ed[i].fr]^dis[ed[i].to]^ed[i].w); } //void dfs(int cr,int f) //{ // vis[cr]=1; // for(int i=head[cr],v;i;i=ed[i].next) // if((v=ed[i].to)!=f) // if(!vis[v]){ // dis[v]=(dis[cr]^ed[i].w);dfs(v,cr); // } // else a[++tot]=(dis[cr]^dis[v]^ed[i].w); //} int ws(ll x) { int ret=0;for(;x;ret++)x>>=1;return ret; } void gauss() { int now; for(int i=1;i<=tot;i++) { if(!a[i])break; int nw=i; for(int j=i+1;j<=tot;j++)if(a[j]>a[nw])nw=j;//>a[nw],不是a[i]... if(nw!=i)swap(a[i],a[nw]); now=ws(a[i])-1; for(int j=1;j<=tot;j++)if(i!=j&&(a[j]&(1ll<<now)))a[j]^=a[i];//上下消 //1ll } } //void gauss() //{ // int nw=0; // for(int i=60;i>=0;i--) // { // int j=nw+1; // for(;j<=tot&&(a[j]&(1ll<<i))==0;j++);//1ll!!! // if(j==tot+1)continue; // nw++; // swap(a[nw],a[j]); // for(int j=1;j<=tot;j++)if(j!=nw&&(a[j]&(1ll<<i)))a[j]^=a[nw]; // } //} int main() { scanf("%d%d",&n,&m);int x,y;ll z; for(int i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&z);add(x,y,z); } sc();/*dfs(1,0);*/ml=dis[n];//不用再dfs一遍求ml gauss(); for(int i=1;i<=tot;i++)ml=max(ml,ml^a[i]);//要这样！ printf("%lld ",ml); return 0; }