\(HDU\) \(5883\) \(The\) \(Best\) \(Path\)
一、题目大意
给你一个 无向图，每个点有权值，你要从某一个点出发，使得 一笔画 经过所有的路，且使得经过的节点的权值XOR运算最大,求最大值。
输入样例
2
3 2
3
4
5
1 2
2 3
4 3
1
2
3
4
1 2
2 3
2 4
答案：
2
Impossible
二、解题思路
异或性质
首先得知道一些关于XOR运算的性质：
-
如果一个数异或偶数次，那么这个结果是\(0\)！
-
如果一个序列是确定的，那么异或的顺序不影响最终的结果！
有了这两个性质，那么这个题就很简单了！
一笔画问题
- ① 如果每个结点的度数为偶数，则能找到一条欧拉回路，且起点（也是终点）是任意的的；
- ② 如果只有两个结点的度数为奇数，其他所有结点的度数为偶数，那么能找到一条欧拉路径，起点为其中一个，终点是另一个。
所以我们可以先统计每个结点的度数，如果有奇数度数的结点个数不是\(2\)或者\(0\)，那么表示不能一笔画。
分数处理
对于异或 同假异真, 所以若某个点经过偶数次,则可以直接不计,只记奇数次的
经过某个点的次数 即为 (度数\(+1\))/\(2\), 所以遍历每个点的度数计算即可
但这样算出来的是源点和汇点不同的情况的
如图从\(1\)到\(3\),\(1\)和\(3\)的度数均为\(1\) 所以\(1\)和\(3\)经过\(\displaystyle \frac{2}{2}=1\)次
\(2\)的度数为\(2\),所以为\(\displaystyle \frac{2+1}{2}=1\) 次
那么源点和汇点相同的怎么算呢
如图,虽然\(1\)和\(3\)之间比上图多了一条边 但是算出来的经过的次数依然和上图的一样\(1\)和\(3\)是\(1\)次 \(2\)也是\(1\)次。
如果没有度数为奇数的点，也就是欧拉回路,出发点终点是同一个点，这样会造成起点的权值被异或干掉
因为欧拉回路可以以任意一个点做为起点和终点，所以，需要枚举一遍，分别尝试以\(i\)这起点，找出最大异或值
\(Code\)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 7;
int n, m;
int a[N];
int d[N];
int main() {
#ifndef ONLINE_JUDGE
freopen("HDU5883.in", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
memset(d, 0, sizeof d);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
d[a]++, d[b]++;
}
// 奇数度点的个数
int cnt = 0;
for (int i = 1; i <= n; i++)
if (d[i] & 1) cnt++;
// 不是0，而且个数不是2，那么肯定没有欧拉通路，也没有欧拉回路
if (cnt && cnt != 2) {
puts("Impossible");
continue;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int x = (d[i] + 1) >> 1;
if (x & 1) ans ^= a[i];
}
// 如果没有度数为奇数的点，也就是欧拉回路,出发点终点是同一个点，这样会造成起点的权值被异或干掉
// 因为欧拉回路可以以任意一个点做为起点和终点，所以，需要枚举一遍，分别尝试以i这起点，找出最大异或值
if (cnt == 0) {
int x = 0;
for (int i = 1; i <= n; i++) x = max(x, ans ^ a[i]);
ans = x;
}
// 输出异或和
printf("%d\n", ans);
}
return 0;
}