You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
## [$HDU$ $5883$ $The$ $Best$ $Path$](http://vjudge.csgrandeur.cn/problem/HDU-5883)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目大意
|
|
|
|
|
|
给你一个 **无向图**，**每个点有权值**，你要从某一个点出发，使得 **一笔画** 经过所有的路，且使得经过的节点的权值`XOR`运算最大,求最大值。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
2
|
|
|
|
|
|
3 2
|
|
|
|
|
|
3
|
|
|
|
|
|
4
|
|
|
|
|
|
5
|
|
|
|
|
|
1 2
|
|
|
|
|
|
2 3
|
|
|
|
|
|
4 3
|
|
|
|
|
|
1
|
|
|
|
|
|
2
|
|
|
|
|
|
3
|
|
|
|
|
|
4
|
|
|
|
|
|
1 2
|
|
|
|
|
|
2 3
|
|
|
|
|
|
2 4
|
|
|
|
|
|
|
|
|
|
|
|
答案：
|
|
|
|
|
|
2
|
|
|
|
|
|
Impossible
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
|
|
|
|
|
|
#### 异或性质
|
|
|
|
|
|
|
|
|
|
|
|
- 如果一个数异或偶数次，结果是$0$
|
|
|
|
|
|
|
|
|
|
|
|
- 如果一个序列是确定的，异或的顺序不影响最终的结果
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 一笔画问题
|
|
|
|
|
|
- ① 如果每个结点的度数为偶数，则能找到一条欧拉回路，且起点（也是终点）是任意的的
|
|
|
|
|
|
- ② 如果只有两个结点的度数为奇数，其他所有结点的度数为偶数，那么能找到一条欧拉路径，起点为其中一个，终点是另一个
|
|
|
|
|
|
|
|
|
|
|
|
所以我们可以先统计每个结点的度数，如果有奇数度数的结点个数不是$2$或者$0$，那么表示不能一笔画。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 分数(点权)处理
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 欧拉回路的处理
|
|
|
|
|
|
如果没有度数为奇数的点，也就是欧拉回路,出发点终点是同一个点，这样会造成起点的权值被异或干掉。
|
|
|
|
|
|
因为欧拉回路可以以任意一个点做为起点和终点，那么选择哪个点做为起点，效果就一样了，因为选择谁就相当于谁要牺牲自己，所以，需要枚举一遍，分别尝试以$i$这起点，找出最大异或值。
|
|
|
|
|
|
|
|
|
|
|
|
### $Code$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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这起点，找出最大异或值
|
|
|
|
|
|
int res = ans;
|
|
|
|
|
|
if (cnt == 0)
|
|
|
|
|
|
for (int i = 1; i <= n; i++) res = max(res, ans ^ a[i]);
|
|
|
|
|
|
// 输出异或和
|
|
|
|
|
|
printf("%d\n", res);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
