The Best Path HDU
图（无向图或有向图）中恰好通过所有边一次且经过所有顶点的的通路成为欧拉通路，图中恰好通过所有边一次且经过所有顶点的回路称为欧拉回路，具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。
规定平凡图（只有一个点）是欧拉图。
性质与定理：
- 无向图G是欧拉图当且仅当G是连通的且没有奇度顶点。
- 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点。
- 有向图D是欧拉图当且仅当D是强连通的且每个顶点恰有两个奇度顶点。
- 有向图D是半欧拉图当且仅当D是单连通的且每个顶点入度等于出度。
显然，该题为求一条欧拉回路或欧拉通路，并求权值异或最大值，我们知道偶数次异或运算结果为0，通过点的度数，我们不难判断出该点参与异或运算的次数，度数为n的点在欧拉回路起始位置被运算的次数为（n + 1）/ 2 + 1，其他情况运算次数为(n + 1) / 2
题目：题目链接
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 6 using namespace std; 7 8 const int maxn = 100000 + 5; 9 10 int n, m, ans; 11 int w[maxn], num[maxn]; 12 13 bool solve(); 14 15 int main() 16 { 17 //freopen("in.txt", "r", stdin); 18 ios::sync_with_stdio(0); 19 cin.tie(0); 20 21 int T, u, v; 22 cin >> T; 23 while(T--) { 24 cin >> n >> m; 25 for(int i = 1; i <= n; ++i) { 26 cin >> w[i]; 27 num[i] = 0; 28 } 29 for(int i = 0; i < m; ++i) { 30 cin >> u >> v; 31 ++num[u]; 32 ++num[v]; 33 } 34 if(solve()) 35 cout << ans << endl; 36 else 37 cout << "Impossible" << endl; 38 } 39 return 0; 40 } 41 42 bool solve() { 43 int sum = 0; 44 for(int i = 1; i <= n; ++i) 45 if(num[i] & 1) 46 ++sum; 47 if(sum != 0 && sum != 2) 48 return false; 49 int temp = 0; 50 for(int i = 1; i <= n; ++i) 51 if((num[i] + 1) >> 1 & 1) 52 temp ^= w[i]; 53 if(sum == 2) 54 ans = temp; 55 else { 56 ans = 0; 57 for(int i = 1; i <= n; ++i) 58 ans = max(ans, temp ^ w[i]); 59 } 60 return true; 61 }