欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj2115 [Wc2011] Xor 线性基

程序员文章站 2022-06-29 21:19:08
...

Description


bzoj2115 [Wc2011] Xor 线性基

Solution


我们发现答案一定是一条路径加上若干个环组成的。注意到一条边被异或两次就没了,因此我们直接选定一条初始路径后不停地加环就行了。求异或和最大考虑用线性基,把环的异或和扔进线性基里面然后随便选一条初始路径即可

关于为什么随便选一条路径是对的,我们感性地发现如果初始路径不够优秀那么异或上一个包含它的环就会变成另一条路径了,即不那么优秀的部分会被消掉

Code


#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)

typedef long long LL;
const int N=50005;

struct Bin {
    LL r[64];

    void ins(LL x) {
        drp(i,63,0) if (x&(1LL<<i)) {
            if (!r[i]) return (void) (r[i]=x);
            x^=r[i];
        }
    }

    LL get_max(LL x) {
        drp(i,63,0) ((r[i]^x)>x)?(x^=r[i]):(0);
        return x;
    }
} B;

struct edge {int y; LL w; int next;} e[100005*2];

int ls[N],edCnt;

LL sum[N];

bool vis[N];

void add_edge(int x,int y,LL w) {
    e[++edCnt]=(edge) {y,w,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {x,w,ls[y]}; ls[y]=edCnt;
}

void dfs(int now,LL tot) {
    vis[now]=true; sum[now]=tot;
    for (int i=ls[now];i;i=e[i].next) {
        if (!vis[e[i].y]) {
            // sum[e[i].y]=sum[now]^e[i].w;
            dfs(e[i].y,tot^e[i].w);
        } else B.ins(sum[e[i].y]^tot^e[i].w);
    }
}

int main(void) {
    freopen("data.in","r",stdin); freopen("myp.out","w",stdout);
    int n,m; scanf("%d%d",&n,&m);
    rep(i,1,m) {
        int x,y; LL w; scanf("%d%d%lld",&x,&y,&w);
        add_edge(x,y,w);
    }
    dfs(1,0);
    printf("%lld\n", B.get_max(sum[n]));
    return 0;
}
相关标签: bzoj