[BZOJ2115] [WC2011] Xor

Description

Input

第一行包含两个整数N和 M， 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

Sample Input

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

6

HINT

Solution

随便整一棵生成树出来，对于每条非树边和树边形成的最小环弄出来跑线性基。

可以很简单的证明图中的每个环都可以通过异或的方式从这些环中异或出来，那么这个线性基其实就是图中所有环的线性基。

然后随便整一条\(1\to n\)的路径，在线性基上跑一下就是答案。

#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;

int head[maxn],tot,dis[maxn],n,m,num[200],vis[maxn];
struct edge{int to,nxt,w;}e[maxn<<1];

void add(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
void ins(int u,int v,int w) {add(u,v,w),add(v,u,w);}

void insert(int x) {
    for(int i=63;~i;i--)
        if((x>>i)&1) {
            if(!num[i]) {num[i]=x;break;}
            x^=num[i];
        }
}

int query(int x) {
    for(int i=63;~i;i--) x=max(x,x^num[i]);
    return x;
}

void dfs(int x) {
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
        if(!vis[e[i].to]) dis[e[i].to]=dis[x]^e[i].w,dfs(e[i].to);
        else insert(dis[e[i].to]^dis[x]^e[i].w);
}

signed main() {
    read(n),read(m);
    for(int i=1,x,y,z;i<=m;i++) read(x),read(y),read(z),ins(x,y,z);
    dfs(1);write(query(dis[n]));
    return 0;
}

[BZOJ2115] [WC2011] Xor

原文：https://www.cnblogs.com/hbyer/p/10572626.html