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

题目描述

XOR（异或）是一种二元逻辑运算，其运算结果当且仅当两个输入的布尔值不相等时才为真，否则为假。 XOR 运算的真值表如下（ $1$ 表示真， $0$ 表示假）：

而两个非负整数的 XOR 是指将它们表示成二进制数，再在对应的二进制位进行 XOR 运算。

譬如 $12$ XOR $9$ 的计算过程如下：

故 $12$ XOR $9 = 5$ 。

容易验证， XOR 运算满足交换律与结合律，故计算若干个数的 XOR 时，不同的计算顺序不会对运算结果造成影响。从而，可以定义 $K$ 个非负整数 $A_1$ ， $A_2$ ，……， $A_{K-1}$ ， $A_K$ 的 XOR 和为

$A_1$ XOR $A_2$ XOR …… XOR $A_{K-1}$ XOR $A_K$

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

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

输入输出格式

输入格式：

输入文件 xor.in 的第一行包含两个整数 $N$ 和 $M$ ，表示该无向图中点的数目与边的数目。

接下来 $M$ 行描述 $M$ 条边，每行三个整数 $S_i$ ， $T_i$ ， $D_i$ ，表示 $S_i$ 与 $T_i$ 之间存在一条权值为 $D_i$ 的无向边。

图中可能有重边或自环。

输出格式：

输出文件 xor.out 仅包含一个整数，表示最大的 XOR 和（十进制结果）。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

【样例说明】

如图，路径 $\rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 5$ 对应的XOR和为

$2$ XOR $1$ XOR $2$ XOR $4$ XOR $1$ XOR $1$ XOR $3 = 6$

当然，一条边数更少的路径 $\rightarrow 3 \rightarrow 5$ 对应的XOR和也是 $2$ XOR $4 = 6$ 。

【数据规模】

对于 $\%$ 的数据， $\leq 100$ ， $\leq 1000$ ， $D_i \leq 10^{4}$ ；

对于 $\%$ 的数据， $\leq 1000$ ， $\leq 10000$ ， $D_i \leq 10^{18}$ ；

对于 $\%$ 的数据， $\leq 5000$ ， $\leq 50000$ ， $D_i \leq 10^{18}$ ；

对于 $\%$ 的数据， $\leq 50000$ ， $\leq 100000$ ， $D_i \leq 10^{18}$ 。

本题思路非常巧妙。因为要找异或最大的路径，我们想到把图上计算转换为序列计算。考虑对于一条已知路径来说，如何可以优化答案。

接下来就非常的巧妙了，我们发现路径上的一条环等价于切换路径！(如图)

上图中，我们做了一下操作：1、任意选择一条从起点到终点的路径。2、选择一个简单环，将环上的边(环点用黄色标出)的选择状态全部取反。这一步操作与将答案异或上环的总权值是等价的(想一想，为什么？)3、重复2的步骤。

那么问题就变为了随意找一条从1到n的路径，每一次可以将路径长度异或上任意一个简单环的权值，问最大是多少。

那么我们只要把所有的简单环找出来不就好了吗？于是这样操作后，这道题就变为了线性基裸题了。

Code:

 #include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const int maxn = 1e5 + 5, maxm = 2e5 + 5;
const LL stmax = 1LL << 62;
struct edge {
    int v, next;LL w;
}e[maxm << 1];
int head[maxn], cnt, n, m, u, v;
LL w;

inline char gc(){
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}

template<class T>
inline void read(T & x) {
    x = 0; static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}

void adde(const int &u, const int &v, const LL &w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}

int vis[maxn], ccnt;
LL cxor[maxm], dis[maxn];
void dfs(int u) {
    vis[u] = 1;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(!vis[v]) dis[v] = dis[u] ^ e[i].w, dfs(v);
        else cxor[++ccnt] = dis[u] ^ dis[v] ^ e[i].w;
    }
}

struct Linear_Base {
    LL LB[70];
    void init() {memset(LB, 0, sizeof(LB));}
    void insert(LL u) {
        for(register LL i = stmax, p = 62; i > 0; i >>= 1, --p) {
            if(!(u & i)) continue;
            if(!LB[p]) {LB[p] = u; break;}
            else u ^= LB[p];
        }
    }
    LL qmax(LL x) {
        for(register int i = 62; i >= 0; --i)
            if((x ^ LB[i]) > x) x ^= LB[i];
        return x;
    }
}A;

int main() {
    read(n), read(m);
    for(register int i = 1; i <= m; ++i)
        read(u), read(v), read(w), adde(u, v, w), adde(v, u, w);
    dfs(1);
    for(register int i = 1; i <= ccnt; ++i) A.insert(cxor[i]);
    printf("%lld", A.qmax(dis[n]));
    return 0;
}

Rockdu's Blog