HDU5883 The Best Path(欧拉回路 | 通路下求XOR的最大值)

本文链接:http://www.cnblogs.com/Ash-ly/p/5932748.html

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5883

思路:

　　先判断原图是否是欧拉回路或者欧拉通路.是的话如果一个点的度数除以2是奇数则可以产生一个XOR贡献值.之后如果是欧拉通路, 则答案是固定的,起点和终点需要多产生一次贡献值. 如果是欧拉回路, 则需要枚举起点.

代码:

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 const int MAXE = ;

 int a[MAXN + ], deg[MAXN + ], pre[MAXN + ], t, n, m;

 int Find(int x) { return x == pre[x] ? x : pre[x] = Find(pre[x]); }

 void mix(int  x, int y) {

     int fx = Find(x), fy = Find(y);

     if(fx != fy) pre[fx] = fy;

 }

 int isEulr(int n) {

     int cnt1 = , cnt2 = ;

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

         if(deg[i] & ) cnt1++;

         if(pre[i] == i) cnt2++;

     }

     if( (cnt1 ==  || cnt1 == ) && cnt2 == ) return cnt1; //cnt1 为 0 代表欧拉回路, 为 2 代表欧拉通路

     return -;

 }

 int main(){
     scanf("%d", &t);

     while(t--) {

         memset(a, , sizeof(a));

         memset(deg, , sizeof(deg));         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; i++) scanf("%d", &a[i]);

         for(int i = ; i <= n; i++) pre[i] = i;

         int u, v, k;

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

             scanf("%d%d", &u, &v);

             deg[u]++, deg[v]++;

             mix(u, v);

         }

         if( (k = isEulr(n) ) >= ) {

             int ans = ;

             for(int i = ; i <= n; i++) ans ^= ( (deg[i] / ) &  ? a[i] :  ) ;

             if(k == )for(int i = ; i <= n; i++)  { if(deg[i] & ) ans ^= a[i]; }//欧拉通路,起点和终点需要多XOR一次

             else  for(int i = ; i <= n; i++)  ans = max(ans, ans ^ a[i]); //欧拉回路, 枚举下起点

             printf("%d\n", ans);

         }

         else printf("Impossible\n");

     }

     return ;

 }