BZOJ2115 [Wc2011] Xor

---

题目描述

传送门

题目分析

需要求最短的XOR路径，可以无限经过点和边。考虑每条路径可能造成的贡献。明显一条边走两次就没贡献了。所以这个题的核心就是在我们到底要经过哪些环。

首先我们XJB确定一个到\(n\)号节点的路径，然后把这个路径的\(XOR\)值当做初始答案，然后对其它所有的环记录下他们的\(XOR\)值，然后放到一起跑个线性基，用线性基的单调性直接跑出最大值。

那么这样为啥是对的，首先一条路走两遍就失去贡献保证了无论这个环长哪里都可以保证稳定提供贡献。然后就是\(XJB\)选的路径如果不是最优，可以有另一条到\(n\)的比它更优的路径和它组成环，然后在这个过程中就可以消除这个的影响。

是代码呢

#include <bits/stdc++.h> using namespace std; const int MAXN=2e5+7; #define ll long long struct po{ll nxt,to,dis; }edge[MAXN<<1]; ll head[MAXN],num,n,m,a[MAXN],p[MAXN],cnt,ans,sum,vis[MAXN],dis[MAXN]; inline void add_edge(int from,int to,ll dis) {edge[++num].nxt=head[from];edge[num].to=to;edge[num].dis=dis;head[from]=num; } inline void dfs(int u,int fa) {vis[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(v==fa) continue;if(!vis[v]) dis[v]=dis[u]^edge[i].dis,dfs(v,u);else a[++cnt]=dis[v]^dis[u]^edge[i].dis;} } inline ll read() {ll x=0,c=1;char ch=' ';while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();while(ch=='-')c*=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*c; } int main() {n=read();m=read();for(int i=1;i<=m;i++){ll x=read(),y=read(),l=read();add_edge(x,y,l);add_edge(y,x,l);}dfs(1,0);ans=dis[n];for(int i=1;i<=cnt;i++){for(int j=63;j>=0;j--){if(!((a[i]>>j)&1)) continue;if(!p[j]){p[j]=a[i];break;}else a[i]^=p[j];}}for(int i=63;i>=0;i--) if((ans^p[i])>ans) ans^=p[i];cout<<ans; }

转载于:https://www.cnblogs.com/victorique/p/10273405.html

总结

以上是生活随笔为你收集整理的BZOJ2115 [Wc2011] Xor的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。