bzoj2115 [Wc2011] Xor 线性基

Description

---

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;
}