BZOJ-2115: [Wc2011] Xor

[文章目录]

Description

给你一张n个点m条边的无向图,求一条1->n的路径,使得路径上的边权亦或和最大。n<=50000 m<=10^5 边权<=10^18

由于是无向图,通过同一条路径走到一个环上再走回来,路径的代价会抵消。那么答案相当于一条1到n的路径和一些环的亦或和。
对于无向图的边集,搜出一个树边集。枚举非树边,对于每个非树边连接到树上和树上的链形成的环记录亦或和,求线性基。答案等于树上1到n的亦或和在线性基中求得的最大值。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
int n,m;
int head[51000],to[201000],nxt[201000],cnt;
ll f[201000];
inline void add(int x,int y,ll z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int fa[51000];
int find(int x){return fa[x]==x ? x:fa[x]=find(fa[x]);}
struct edge
{
    int a,b;
    ll w;
}a[101000];
ll dep[51000],lin[100];
void dfs(int x,int pre)
{
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        dep[to[i]]=dep[x]^f[i];
        dfs(to[i],x);
    }
}
void insert(ll x)
{
    for(int i=62;i>=0;--i) if(x&(1ll<<i))//NOTE: 1+"ll" How foolish I am!
    {
        if(lin[i]) x^=lin[i];
        else {lin[i]=x; break;}
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int i; for(i=1;i<=n;++i) fa[i]=i;
    i=1;
    while(i<=m)
    {
        scanf("%d%d%llu",&a[i].a,&a[i].b,&a[i].w);
        if(find(a[i].a)!=find(a[i].b))
        {
            add(a[i].a,a[i].b,a[i].w);
            fa[find(a[i].a)]=find(a[i].b);
            --m;
        }
        else ++i;
    }
    dfs(1,0);
    for(i=1;i<=m;++i) insert(a[i].w^dep[a[i].a]^dep[a[i].b]);
    ll ans=dep[n];
    for(i=62;~i;--i) if((ans^lin[i])>ans) ans^=lin[i];
    printf("%llu\n",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注