考虑一个边权为非负整数的无向连通图，节点编号为 $1$ 到 $N$ ，试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得路径上经过的边的权值的 $\text{XOR}$ 和最大。
路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 $\text{XOR}$ 和时也要被计算相应多的次数。
图中可能有重边或自环。
链接
Luogu P4151
题解
一个有可能比较常见的套路：
考虑 $1\rightarrow n$ 的路径，一定由一条路径和一些环获得。
我们注意到考虑挂在路径上的环的影响时，不必考虑环如何到达路径，因为我们必然有一条路径使得“去环”和“离开环”恰好抵消。因此我们可以随便加环。
我们甚至还注意到，$1\rightarrow n$ 路径也可以随便选，因为如果是另一条路径的话，事实上异或一个经过 $1$ 和 $n$ 的大环就可以得到另一条 $1 \rightarrow n$ 的路径了。
找环就用 dfs ，其中每一条返祖边都可以对应一个环。即使是有公共边的环也可以用小环异或出来，所以返祖边直接处理环即可。
时间复杂度 $O(n \times 64)$.
代码
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
| #include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 51000,MAXM = 110000,logn = 61;
struct LB{
ll basis[logn];
void insert(ll x){
if(!x) return;
for(int i = logn-1;i>=0;--i){
if((x & (1LL<<i)) == 0) continue;
if(basis[i] == 0){
basis[i] = x;
break;
}
else{
x ^= basis[i];
}
}
}
ll getmax(ll ans = 0){
for(int i = logn-1;i>=0;--i){
if((ans^basis[i]) > ans){
ans ^= basis[i];
}
}
return ans;
}
}B;
struct Edge{
int to,nex;
ll len;
}edge[MAXM*2];
int fir[MAXN],ecnt = 2;
void addedge(int a,int b,ll c){
edge[ecnt] = (Edge){b,fir[a],c};
fir[a] = ecnt++;
}
int n,m;
void init(){
scanf("%d %d",&n,&m);
int a,b;ll c;
for(int i = 1;i<=m;i++){
scanf("%d %d %lld",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
}
ll dis[MAXN];bool vis[MAXN];
void dfs(int nown){
vis[nown] = 1;
for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
int v = edge[nowe].to;ll len = edge[nowe].len;
if(vis[v] == 1){
B.insert(dis[nown]^dis[v]^len);
}
else{
dis[v] = dis[nown] ^ len;
dfs(v);
}
}
}
void solve(){
dfs(1);
printf("%lld\n",B.getmax(dis[n]));
}
int main(){
init();
solve();
return 0;
}
|
