首页 > 代码库 > BZOJ2115 WC2011 Xor DFS+高斯消元
BZOJ2115 WC2011 Xor DFS+高斯消元
题意：给定一张无向图，求1到N异或和最大的路径，允许重复经过。
题解：首先跑出1到N的一条路径，答案就是在这条路径上不断加环。首先用DFS处理出所有基环的异或和（其他环一定由基环构成，重复部分异或之后就会消掉），然后就是从一堆数里选任意个数使得异或和最小了，怎么做可以去看莫涛的课件（同解01异或方程），这里我简单介绍一下。
通过高斯消元，我们对原来的数进行操作，使得所有原来的数都可以用操作之后的数来组合而成（这玩意貌似叫线性基啊）。具体做法就是从高到低暴力枚举每一位i，找到一个第i位为1的数j，然后将所有除这个数外第i位为1的数x^=j，最后消出来的b就是线性基了。直观看起来很显然，具体的证明我也不会QAQ。
然后可以暴力枚举，看某个环是不是要加进去了。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=50000+2;const int MAXM=100000+2;struct HASH{ int u; ll w; HASH *next; HASH(){} HASH(int _u,ll _w,HASH *_next):u(_u),w(_w),next(_next){}}*table[MAXN],mem[MAXM];int N,M,C,cnt;ll ans,d[MAXN],w[2*MAXM];bool flag[MAXN];void Insert(int u,int v,ll w){ table[u]=&(mem[cnt++]=HASH(v,w,table[u]));}void DFS(int x){ flag[x]=1; for(HASH *p=table[x];p;p=p->next) if(!flag[p->u]) d[p->u]=d[x]^p->w,DFS(p->u); else cnt++,w[cnt]=d[x]^d[p->u]^p->w;}void Gauss(){ ll i=1; for(int j=60;j;j--) i<<=1; for(;i;i>>=1){ int j=C+1; while(j<=cnt && !(w[j]&i)) j++; if(j>cnt) continue; C++; swap(w[C],w[j]); for(int k=1;k<=cnt;k++) if(k!=C && (w[k]&i)) w[k]^=w[C]; }}int main(){ cin >> N >> M; for(int i=1;i<=M;i++){ int a,b;ll c; scanf("%d %d %lld",&a,&b,&c); Insert(a,b,c),Insert(b,a,c); } cnt=0,DFS(1); Gauss(),ans=d[N]; for(int i=1;i<=C;i++) ans=max(ans,ans^w[i]); cout << ans << endl; return 0;}
BZOJ2115 WC2011 Xor DFS+高斯消元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。