正题
题目链接:https://www.luogu.com.cn/problem/P4151
题目大意
给一个无向图，求一条
1
∼
n
1\sim n
1∼n的路径使得异或和最大。
解题思路
很强的思路啊（好像去年
Y
P
X
YPX
YPX大爷就讲了反正我也没听懂）
我们可以将路径拆分成三部分：环，连接环的路径，连接
1
1
1和
n
n
n的路径。其中连接环的路径因为会走两次所以就不用处理。
那我们发现如果
1
1
1点能到的环可以任意我们选择异或或者不异或，也就是对于每个环我们可以丢入线性基中处理。
考虑
1
1
1到
n
n
n的路径如何选择，我们发现对于两条
1
1
1到
n
n
n的路径会构成一个环，也就是如果我们选择了不优的那一条，那么只要异或上这个大环就可以了。所以我们随便选择一条
1
1
1到
n
n
n的路径即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
const ll N
=5e4+10;
struct node
{
ll to
,next
,w
;
}a
[N
*4];
ll n
,m
,tot
,d
[80],v
[N
],w
[N
],ls
[N
];
void add(ll x
){
for(ll i
=60;i
>=0;i
--)
if((x
>>i
)&1){
if(d
[i
])x
^=d
[i
];
else{
d
[i
]=x
;
break;
}
}
return;
}
void addl(ll x
,ll y
,ll w
){
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
a
[tot
].w
=w
;
return;
}
void dfs(ll x
,ll dis
){
v
[x
]=1;w
[x
]=dis
;
for(ll i
=ls
[x
];i
;i
=a
[i
].next
){
ll y
=a
[i
].to
;
if(v
[y
])add(dis
^a
[i
].w
^w
[y
]);
else dfs(y
,dis
^a
[i
].w
);
}
return;
}
ll
solve(ll ans
){
for(ll i
=60;i
>=0;i
--)
if((ans
^d
[i
])>ans
)ans
^=d
[i
];
return ans
;
}
int main()
{
scanf("%lld%lld",&n
,&m
);
for(ll i
=1;i
<=m
;i
++){
ll x
,y
,w
;
scanf("%lld%lld%lld",&x
,&y
,&w
);
addl(x
,y
,w
);addl(y
,x
,w
);
}
dfs(1,0);
printf("%lld",solve(w
[n
]));
}
