XorTravelingSalesman

作者：陈通 徐明宽

关键词：异或 记忆化搜索

试题来源

Topcoder SRM 556 Div1 250

试题大意

给一个包含$n$个点的图，两点间可能没有边或有一条双向边相连，边用数组$roads[i][j]$表示。点的编号为$0$到$n-1$，每个点有一个权值，第$i$个点的权值为$cityValue_i$。你从$0$号点出发开始旅行，可以沿着边走到相邻的点，一个点可以经过多次，你可以在任何一点结束旅行。初始时，你在$0$号点且你的收益为$cityValue_0$，你每经过一个点，你的收益就会与当前点的权值异或。你的最终收益为你结束旅行时的收益。求最终收益的最大值。

$1 \leq n \leq 50$，$0 \leq cityValue \leq 1023$

算法介绍

算法一

此题可以用记忆化搜索求解。定义状态$f[i][j]$，表示是否存在某一时刻你处在$i$号点，且当前权值为$j$。初值$f[0][cityValue_0] = true$。对每个为$true$的状态进行扩展，若状态$f[i][j] = true$，则对于每一个与$i$有边相连的点$x$，有$f[x][j \ XOR \ cityValue_x] = true$。最终答案即为使得$f[i][j] = true$成立的最大的$j$。

易知状态总数为$n \times cityValue$，在搜索的过程中每个状态只会扩展一次，所以总时间复杂度为$O(n^2cityValue)$。

算法二

先说结论：当$0$号点的度为$0$时，显然答案为$cityValue_0$；否则，对于任意一个$0$号点所在连通块的子集，可以构造一条路径，使得最终收益为这个子集里的点权的异或和。

证明：初始时在$0$号点且收益为$cityValue_0$。对于任意点$i \in$目标集合且$i \neq 0$，存在一条从点$0$到点$i$的路径，于是可以从点$0$沿相同的路径走到点$i$再走回点$0$，这样收益就异或上了$cityValue_0 \ XOR \ cityValue_i$。处理完除了$0$号点以外的所有目标集合中的点以后，如果收益不等于目标集合里的点权异或和，那么收益一定等于目标集合里的点权异或和与$cityValue_0$的异或，此时可以任取一个与$0$号点有边直接相连的点$j$，从点$0$走到点$j$再走到点$0$再走到点$j$，这样收益会依次异或上$cityValue_j$、$cityValue_0$、$cityValue_j$，也就满足要求了。

有了这个结论以后，这道题就转化成了经典的最大异或和问题（给定$n$个数，选取若干个数使异或和最大）（当$0$号点的度为$0$时，由于$cityValue_0$非负，所以答案也是最大异或和），可以用高斯消元（按位贪心）的方法在$O(n \log{cityValue})$的时间复杂度内解决。