M_sea

洛谷4151 [WC2011]最大XOR和路径
LuoguBZOJ分析萌新求助,刚学线性基,请问......首先,发现一个环上的异或和是可以直接获得的。因为你可以...
扫描右侧二维码阅读全文
13
2019/02

洛谷4151 [WC2011]最大XOR和路径

Luogu

BZOJ

分析

萌新求助,刚学线性基,请问......

首先,发现一个环上的异或和是可以直接获得的。

因为你可以走一条路径到环,绕环一圈,再走这条路径回来。

于是把环上的异或和丢到线性基里去,然后随便找一条$1\sim n$的路径,假设它的异或和为$x$。

直接到线性基里去查询与$x$异或的最大值就行了。

注意$\texttt{long long}$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

template<typename T>
inline void read(T& X) {
    X=0; int w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    X*=w;
}

const int L=60;
const int N=50000+10;
const int M=100000+10;

struct LinearBasis {
    ll a[L+1];
    LinearBasis() { memset(a,0,sizeof(a)); }
    inline void insert(ll t) {
        for (re int i=L;i>=0;--i) {
            if (!(t&(1ll<<i))) continue;
            if (a[i]) t^=a[i];
            else { a[i]=t; return; }
        }
    }
    inline ll queryMax(ll ans=0) {
        for (re int i=L;i>=0;--i)
            if ((ans^a[i])>ans) ans^=a[i];
        return ans;
    }
} G;

int n,m;
struct Edge { int v,nxt; ll w; } e[M<<1];
int head[N];

inline void addEdge(int u,int v,ll w) {
    static int cnt=0;
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int vis[N];
ll dis[N];

inline void dfs(int u) {
    vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; ll w=e[i].w;
        if (vis[v]) G.insert(dis[u]^dis[v]^w);
        else dis[v]=dis[u]^w,dfs(v);
    }
}

int main() {
    read(n),read(m);
    for (re int i=1;i<=m;++i) {
        int u,v; ll w; read(u),read(v),read(w);
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dfs(1); printf("%lld\n",G.queryMax(dis[n]));
    return 0;
}
最后修改:2019 年 02 月 13 日 08 : 45 AM

1 条评论

  1. smy

    %%%

发表评论