The Best Path HDU - 5883 欧拉通路

　　图（无向图或有向图）中恰好通过所有边一次且经过所有顶点的的通路成为欧拉通路，图中恰好通过所有边一次且经过所有顶点的回路称为欧拉回路，具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。

　　规定平凡图（只有一个点）是欧拉图。

性质与定理：

1. 无向图G是欧拉图当且仅当G是连通的且没有奇度顶点。
2. 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点。
3. 有向图D是欧拉图当且仅当D是强连通的且每个顶点恰有两个奇度顶点。
4. 有向图D是半欧拉图当且仅当D是单连通的且每个顶点入度等于出度。

显然，该题为求一条欧拉回路或欧拉通路，并求权值异或最大值，我们知道偶数次异或运算结果为0，通过点的度数，我们不难判断出该点参与异或运算的次数，度数为n的点在欧拉回路起始位置被运算的次数为（n + 1）/ 2 + 1，其他情况运算次数为(n + 1) / 2

题目：题目链接

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int n, m, ans;

 int w[maxn], num[maxn];

 bool solve();

 int main()

 {

     //freopen("in.txt", "r", stdin);

     ios::sync_with_stdio();

     cin.tie();

     int T, u, v;

     cin >> T;

     while(T--) {

         cin >> n >> m;

         for(int i = ; i <= n; ++i) {

             cin >> w[i];

             num[i] = ;

         }

         for(int i = ; i < m; ++i) {

             cin >> u >> v;

             ++num[u];

             ++num[v];

         }

         if(solve())

             cout << ans << endl;

         else

             cout << "Impossible" << endl;

     }

     return ;

 }

 bool solve() {

     int sum = ;

     for(int i = ; i <= n; ++i)

         if(num[i] & )

             ++sum;

     if(sum !=  && sum != )

         return false;

     int temp = ;

     for(int i = ; i <= n; ++i)

         if((num[i] + ) >>  & )

             temp ^= w[i];

     if(sum == )

         ans = temp;

     else {

         ans = ;

         for(int i = ; i <= n; ++i)

             ans = max(ans, temp ^ w[i]);

     }

     return true;

 }