[洛谷 4151][WC2011]最大 XOR 和路径

题目链接

https://www.luogu.com.cn/problem/P4151

题解

一条边经过两次后，这条边就对答案没有贡献了。

但是通过这条边，我们可以到达某些新边，从而将新边的答案计入贡献中。

比如一条边连着一个环的情况，在这种情况下，如果我们经过了这个环，连接这个环的边不会对答案产生贡献，但是这个环的贡献算入了答案中。

这样我们有了一种思路：将答案分为两部分，一部分是 \(1 \to n\) 的路径，另一部分是我们可以到达的环。在包含 \(1 \to n\) 的路径的贡献前提下，我们求的是环的子集与链的最大异或和。

从 \(1 \to n\) 的路径有很多条，选哪一条链呢？事实上随便选一条就可以。

原因是：从 \(1 \to n\) 的若干条路径也组成了环，如果我们选了一条路径，后面发现另外一条路径更优的话，我们只需选包含这两条路径的环，从而将原来路径的贡献消去，变成新路径的贡献。

#include <iostream>
using namespace std;
struct edge
{
 int v,next;
 long long w;
}e[200005];
int head[50005],vis[50005],cnt;
long long res[50005],p[65];
void add(long long x)
{
 for(int i=63;i>=0;i--)
  if((x>>i)&1)
  {
   if(!p[i])
   {
    p[i]=x;
    return;
   }
   else x^=p[i];
  }
}
long long query(long long x)
{
 for(int i=63;i>=0;i--)
  if((x^p[i])>x)x^=p[i];
 return x;
}
void addedge(int u,int v,long long w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dfs(int u,long long w)
{
 vis[u]=1;
 res[u]=w;
 for(int i=head[u];i;i=e[i].next)
 {
  int v=e[i].v;
  if(vis[v])add(w^e[i].w^res[v]);
  else dfs(v,w^e[i].w);
 }
}
int main()
{
 int n,m;
 cin>>n>>m;
 for(int i=1;i<=m;i++)
 {
  int u,v;
  long long w;
  cin>>u>>v>>w;
  addedge(u,v,w);
  addedge(v,u,w);
 }
 dfs(1,0);
 cout<<query(res[n])<<endl;
 return 0;
}