[线性基] Luogu P4151 最大XOR和路径题解代码

68 阅读 0 评论 45 点赞

我是靠谱客的博主坚定金毛，最近开发中收集的这篇文章主要介绍[线性基] Luogu P4151 最大XOR和路径题解代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

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

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

譬如

故

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

$A_1A1 XOR A_2A2 XOR …… XOR A_{K-1}AK−1 XOR A_KAK$

考虑一个边权为非负整数的无向连通图，节点编号为

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

输入输出格式

输入格式：

输入文件 xor.in 的第一行包含两个整数

接下来 $S_iSi， T_iTi ， D_iDi，表示 S_iSi 与 T_iTi 之间存在一条权值为 D_iDi 的无向边。$

图中可能有重边或自环。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【样例说明】

如图，路径

当然，一条边数更少的路径

【数据规模】

对于 $1000M≤1000，D_i leq 10^{4}Di≤104；$

对于 $10000M≤10000，D_i leq 10^{18}Di≤1018；$

对于 $50000M≤50000，D_i leq 10^{18}Di≤1018；$

对于 $100000M≤100000，D_i leq 10^{18}Di≤1018。$

题解

任意一条1
然后就好做了

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define ll long long
 5 using namespace std;
 6 const ll N=110,M=50010;
 7 ll n,m,cnt,vis[M],head[M*2],dis[M],mi[N],b[N];
 8 struct edge{ ll from,to,v; }e[M*4];
 9 void insert(ll x,ll y,ll v)
10 {
11     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].v=v;
12     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt,e[cnt].v=v;
13 }
14 void update(ll x) { for (ll i=60;i>=0;i--) if (mi[i]&x) { if (b[i]) x^=b[i]; else { b[i]=x; break; } } }
15 void dfs(ll x)
16 {
17     vis[x]=1;
18     for (ll i=head[x];i;i=e[i].from) if (vis[e[i].to]) update(dis[e[i].to]^e[i].v^dis[x]); else dis[e[i].to]=dis[x]^e[i].v,dfs(e[i].to);
19 }
20 ll query(ll x)
21 {
22     ll ans=x;
23     for (ll i=60;i>=0;i--) ans=max(ans,ans^b[i]);
24     return ans;
25 }
26 int main()
27 {
28     scanf("%lld%lld",&n,&m);
29     mi[0]=1; for (ll i=1;i<=60;i++) mi[i]=mi[i-1]*2;
30     for (ll i=1,x,y,z;i<=m;i++) scanf("%lld%lld%lld",&x,&y,&z),insert(x,y,z);
31     dfs(1),printf("%lld",query(dis[n]));    
32 }