题解 P4151 【[WC2011]最大XOR和路径】

· · 题解

我的主页（阅读效果更好）打开即可RP++

题目要求很多条边的最大异或和，从这一点我们可以想到线性基。这里归纳一下线性基的几点性质：

设V是某个神奇的向量空间，B是V的基，则B应满足以下条件：

1.V是B的极小生成集，就是说只有B能张成V，而它的任何真子集都不张成全部的向量空间。

2.B是V中线性无关向量的极大集合，就是说B在V中是线性无关集合，而且V中没有其他线性无关集合包含它作为真子集。

3.V中所有的向量都可以按唯一的方式表达为B中向量的线性组合。

这也就是说，我们可以用不超过log_{2}{m}个基就能表示所有的异或和，考虑题目中一句重要的话：

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

这句话给了我们一点启发，假设某条路k被重复走了两次，那么它的权值对答案的贡献就是0，但是通过这条路径k，我们可以到达它连接的另一个点。

显然我们没法枚举1~N的每一条路，但我们可以将路径拆成两部分，第一部分是环，第二部分是链。

假设我们选择了一条从1~N的链，当然，它不一定是最优秀的。但是别忘了，我们可以选择一些环来增广这条链。举个例子：

假设k是连接这条链和某个环的某条路径，那么显然，链和环都将走过一遍，而这条路径k会被走过两遍（从链到环一遍，从环到链一遍）。根据我们上面的推论，k对答案的贡献是0。于是我们发现，我们根本就没有必要算出这条路径k！（反正贡献是0）

于是我们枚举所有环，将环上异或和扔进线性基，然后用这条链作为初值，求线性基与这条链的最大异或和。

void dfs(int u,LL res) {//枚举所有环
    del[u]=res,vis[u]=1;
    for (int i=head[u];i;i=e[i].next)
        if (!vis[e[i].to]) dfs(e[i].to,res^e[i].w);
        else insert(res^e[i].w^del[e[i].to]);
}
LL query(LL x) {//最大异或和
    LL res=x;
    for (int i=63;i>=0;i--)
        if ((res^num[i])>res)
            res^=num[i];
    return res;
}

最后说一下怎么选最开始的这条链，其实它可以随便选。我们考虑以下这种情况：

假设路径A比路径B优秀一些，而我们最开始选择了路径B。显然，A与B共同构成了一个环。如果我们发现路径A要优秀一些，那么我们用B异或上这个大环，就会得到我们想要的A！

所以这道题的算法是：找出所有环，扔进线性基，随便找一条链，以它作为初值求最大异或和就可以了。

附上AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
LL num[70];
bool insert(LL x) {
    for (int i=63;i>=0;i--)
        if ((x>>i)&1) {
            if (!num[i]) {
                num[i]=x;
                return true;
            }
            x^=num[i];
        }
    return false;
}
LL query(LL x) {
    LL res=x;
    for (int i=63;i>=0;i--)
        if ((res^num[i])>res)
            res^=num[i];
    return res;
}
struct edge {
    int to,next;
    LL w;
}e[200010];
int head[50010],ecnt;
inline void adde(int from,int to,LL w) {
    e[++ecnt]=(edge){to,head[from],w},head[from]=ecnt;
    e[++ecnt]=(edge){from,head[to],w},head[to]=ecnt;
}
int vis[50010];LL del[50010];
void dfs(int u,LL res) {
    del[u]=res,vis[u]=1;
    for (int i=head[u];i;i=e[i].next)
        if (!vis[e[i].to]) dfs(e[i].to,res^e[i].w);
        else insert(res^e[i].w^del[e[i].to]);
}
int main() {
    int n,m,a,b;LL c;scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d%lld",&a,&b,&c),adde(a,b,c);
    dfs(1,0);
    printf("%lld\n",query(del[n]));
}