问题描述:

考虑一个边权为非负整数的无向连通图,节点编号为$1$到$N$,试求出一条从 $1$号节点到$N$号节点的路径,使得路径上经过的边的权值的 XOR 和最大。

路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 XOR 和时也要被计算相应多的次数。

输入:

第一行包含两个整数$N(n<=50000)$和$M(m<=100000)$,表示该无向图中点的数目与边的数目。
接下来$M$行描述$M$条边,每行三个整数$S_i,T_i,D_i$,表示$S_i$与$T_i$之间存在一条权值为$D_i$的无向边(图中可能有重边或自环)

输出:

仅包含一个整数,表示最大的 XOR 和

思路:

这种玄学的做法自然的想不到的啦。。。

首先异或路径有一个很有趣的地方就是你可以“瞬移”到任何地方,严谨的说就是你从$x$到$y$,再从$y$回到$x$这一段路径对答案的贡献为0。所以你从1到n的路径可以看成是:一条1到n的简单路径加上图中的一些环。形象的说就是你可以瞬移到环上一点绕一圈再瞬移回来。

如果只有一条1到n的路径,我们就可以直接利用线性基求出它们的最大异或和就好了。但如果有多条路径该如何维护?其实这也很简(xuan)单(xue),随意选任意一条就好了!!因为这多条路径其实是构成了多个环的,如果你选了一条使答案更小路径,那么你再选这个路径构成的环就好了。那条小的路径走了两遍,相当于你走了另一条路径。所以你可以随意选一条路径,同样用线性基维护就好了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
#define LL long long
using namespace std;

int n, m, cnt, tot, head[MAXN];
LL ans, dis[MAXN], cir[MAXN], base[MAXN];
bool vis[MAXN];

struct Edge {int next, to; LL dis;} edge[MAXN*2];

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void insert(LL x)
{
    for(int i=62; i>=0; i--)
    {
        if(!(x>>i)) continue;
        if(!base[i])  {base[i]=x; break;}
        x^=base[i];
    }
}

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    dfs(1);
    ans=dis[n];
    for(int i=62; i>=0; i--)
        if((ans^base[i])>ans) ans=ans^base[i];
    printf("%lld\n", ans);
}

发表评论

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