首页 > 代码库 > BZOJ 2115: [Wc2011] Xor [高斯消元XOR 线性基 图]
BZOJ 2115: [Wc2011] Xor [高斯消元XOR 线性基 图]
啦啦啦
题意：
N 个点M条边的边带权的无向图，求1到n一条XOR和最大的路径
感觉把学的东西都用上了....
1到n的所有路径可以由一条1到n的简单路径异或上任意个简单环得到
证明：
如果环与路径有交，异或后那块交就没了，相当于那块走了环上的路径；
如果环与路径没交，就是走到环上走一圈在回来，一去一回其他的地方又没了。
求一棵生成树，然后每一条非树边构成一个环，一共$m-n+1$个环
然后答案就是任取一些环的异或和与1到n路径异或和异或的最大值啦
实现上注意：
1.求生成树和简单环的异或和一遍DFS就可以
2.因为加了无向边，所以一条非树边可能贡献了两个方程，空间要开两倍(或者标记一下)
3.最后求最大值两种写法
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <bitset>using namespace std;typedef long long ll;const int N=5e4+5,M=1e5+5,INF=1e9;inline ll read(){ char c=getchar();ll x=0; while(c<‘0‘||c>‘9‘){c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x;}int n,m,u,v,p;ll w,a[M],bin[62];struct edge{ int u,v,ne; ll w;}e[M<<1];int h[N],cnt;inline void ins(int u,int v,ll w){ cnt++; e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].u=v;e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}ll d[N];bool vis[N],use[M<<1];void dfs(int u){ vis[u]=1; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]){ d[v]=d[u]^e[i].w; dfs(v); }else if(!use[((i-1)^1)+1]) a[++p]=d[u]^d[v]^e[i].w,use[i]=1; }}void ini(){ bin[0]=1;for(int i=1;i<=60;i++) bin[i]=bin[i-1]<<1;}int now,pivot[N];void Gauss(int n){ now=1; for(int i=60;i>=0;i--){ int j=now; while(j<=n&&!(a[j]&bin[i])) j++; if(j==n+1) continue; if(j!=now) swap(a[j],a[now]); for(int k=1;k<=n;k++) if(k!=now&&(a[k]&bin[i])) a[k]^=a[now]; pivot[i]=now; now++; } now--;}int main(){ freopen("in","r",stdin); ini(); n=read();m=read(); for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w); dfs(1); Gauss(p); ll b=d[n]; //printf("dn %lld\n",d[n]); for(int i=60;i>=0;i--) if(!(b&bin[i])) b^=a[pivot[i]]; //for(int i=1;i<=now;i++) b=max(b,b^a[i]); printf("%lld\n",b);}
BZOJ 2115: [Wc2011] Xor [高斯消元XOR 线性基 图]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。