BZOJ2115 [Wc2011] Xor 线性基+DFS

发布于 2017-12-22  3.83k 次阅读


题目

 

给出一个无向图,求一条1-n的路径,使路径边权xor和最大。

首先,可以把一条简单路径和任意多个环拼在一起,形成一条题目所求的路径。接着,对于任意一条简单路径,都可以和一些环的权值异或在一起,达到其他简单路径的效果。所以,我们只需找出任意一条简单路径,找到所有的环,再把环上的xor值都加入线性基,之后查询和当前路径抑或最大值即可,可以使用线性基按位贪心,求出最大值。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974