BZOJ 2115 [Wc2011] Xor

本文主要是介绍BZOJ 2115 [Wc2011] Xor，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定边权为非负的无向图，求1到n边权异或和最大的路径（可以重复经过点和边）。
$n≤50000,m≤100000,0≤e_i≤10^{18}$

PoPoQQQ:
http://blog.csdn.net/popoqqq/article/details/39804075
一条路径的异或和可以化为一条1到n的简单路径和一些简单环的异或和，我们首先DFS求出任意一条1到n的简单路径以及图中所有线性无关的环（线性基）。

度娘:
1.线性基能相互异或得到原集合的所有相互异或得到的值。
2.线性基是满足性质1的最小的集合。
3.线性基没有异或和为0的子集。

用高斯消元求线性基，其结果的特点是最高位单调，且每个数的最高位只出现在这个数上。
(e.g 110,011->101,011)

最后贪心求解即可。

线性基+dfs生成树

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template<class T>void sc(T &x){int f=1;x=0;char c;while(c=getchar(),c<48)if(c=='-')f=-1;do x=x*10+(c^48);while(c=getchar(),c>47);x*=f;
}
template<class T>void nt(T x){if(!x)return;nt(x/10);putchar('0'+x%10);
}
template<class T>void pt(T x){if(x<0){putchar('-');x=-x;}if(!x)putchar('0');else nt(x);
}
//----------------------------
const int maxn=50004;
const int maxm=100005;int n,m;int last[maxm],ecnt;
struct Edge{int to;ll w;int nxt;
}edge[maxm<<1];
void ins(int u,int v,ll w){edge[++ecnt]=(Edge){v,w,last[u]};last[u]=ecnt;
}ll d[maxm<<1];//*
ll key[maxn];
int tot;
bool vis[maxn];
void dfs(int x){vis[x]=true;for(int i=last[x];i;i=edge[i].nxt){int y=edge[i].to;if(vis[y]){ll t=key[x]^key[y]^edge[i].w;if(t)d[++tot]=t;}else{key[y]=key[x]^edge[i].w;dfs(y);}}
}
void gospoly(){int i,k=0;for(ll t=1ll<<62;t;t>>=1){for(i=k+1;i<=tot;i++)if(d[i]&t)break;if(i>tot)continue;swap(d[++k],d[i]);for(int j=1;j<=tot;j++)if(j!=k&&(d[j]&t))d[j]^=d[k];}
}int main(){sc(n);sc(m);ll w;for(int u,v,i=1;i<=m;i++){sc(u);sc(v);sc(w);ins(u,v,w);ins(v,u,w);}dfs(1);gospoly();ll ans=key[n];for(int i=1;d[i];i++)if((ans^d[i])>ans)ans^=d[i];printf("%lld\n",ans);return 0;
}

这篇关于BZOJ 2115 [Wc2011] Xor的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---