首页 > 代码库 > BZOJ2115 WC2011 Xor DFS+高斯消元

BZOJ2115 WC2011 Xor DFS+高斯消元

2024-09-06 01:21:58   218人阅读

题意：给定一张无向图，求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;}
View Code

 

BZOJ2115 WC2011 Xor DFS+高斯消元


联系
我们