「Luogu P4151」[WC2011]最大XOR和路径 - 线性基

给定一张无向带权图,有重边和自环

求从 1 走到 N 的路径最大异或和

水知乎时看到莫队的评论提到了这道题,遂来水了(逃

链接

「Luogu P4151」

题解

假设当前已经找到了一条 1 走到 N 的非最优解路径

这时想到题目中提到有重边和自环

于是考虑利用异或的性质进行增广

一条链 + 一个环 可以对答案贡献一个环的异或和

因为链走过去走回来异或下就抵消了

所以搜索一下枚举每个环加入线性基即可

话不多说看代码

然后就水了一道黑题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>

typedef long long LL;

const int N = 5e4 + 5;
const int M = 2e5 + 5;

int n, m, num_edge, head[N];
LL dis[N];
bool vis[N];

struct Edge
{
int next, to;
LL dis;
} edge[M];

void add_edge(int u, int v, LL dist)
{
edge[++num_edge].next = head[u];
edge[num_edge].to = v;
edge[num_edge].dis = dist;
head[u] = num_edge;
}

class Linear_Base
{
private:
static const int LogN = 63;
LL a[LogN + 5];

public:
void insert(LL x)
{
for (int i = LogN; i >= 0; i--)
if (x & (1LL << i))
if (!a[i])
{
a[i] = x;
return;
}
else
x ^= a[i];
}
LL query_max(LL x)
{
LL res = x;
for (int i = LogN; i >= 0; i--)
if ((res ^ a[i]) > res)
res ^= a[i];
return res;
}
} LB;

void DFS(int u, LL res)
{
dis[u] = res;
vis[u] = true;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
LL dist = edge[i].dis;
if (!vis[v])
DFS(v, res ^ dist);
else
LB.insert(dis[v] ^ res ^ dist);
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
LL dist;
scanf("%d%d%lld", &u, &v, &dist);
add_edge(u, v, dist);
add_edge(v, u, dist);
}
DFS(1, 0);
printf("%lld", LB.query_max(dis[n]));
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×