python/TangDou/AcWing/EulerPath/HDU5883.md

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

二、解题思路

异或性质

• 如果一个数异或偶数次，结果是0

• 如果一个序列是确定的，异或的顺序不影响最终的结果

一笔画问题

• ① 如果每个结点的度数为偶数，则能找到一条欧拉回路，且起点（也是终点）是任意的的
• ② 如果只有两个结点的度数为奇数，其他所有结点的度数为偶数，那么能找到一条欧拉路径，起点为其中一个，终点是另一个

所以我们可以先统计每个结点的度数，如果有奇数度数的结点个数不是2或者0，那么表示不能一笔画。

分数(点权)处理

欧拉回路的处理

如果没有度数为奇数的点，也就是欧拉回路,出发点终点是同一个点，这样会造成起点的权值被异或干掉。 因为欧拉回路可以以任意一个点做为起点和终点，那么选择哪个点做为起点，效果就一样了，因为选择谁就相当于谁要牺牲自己，所以，需要枚举一遍，分别尝试以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这起点，找出最大异或值
        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;
}