首页 > 代码库 > hdu5883(欧拉路)

hdu5883(欧拉路)

比赛第一遍做的时候没有考虑回路要枚举起点的情况导致WA了一发orz

节点 i 的贡献为((du[i] / 2) % 2)* a[i]

欧拉回路的起点贡献多一次,欧拉通路起点和终点也多一次。

代码如下:

 1 #include<cstring> 2 #include<algorithm> 3 #include<queue> 4 #include<vector> 5 #include<set> 6 #define CLR(a,b) memset((a),(b),sizeof((a))) 7 using namespace std; 8  9 const int N = 100003;10 const int inf = 0x3f3f3f3f;11 int n, m;12 int a[N];13 int du[N];14 15 int main(){16     int t, i, j, b, c, f, ans, dd, ma;17     scanf("%d", &t);18     while(t--){19         ans = 0;20         scanf("%d %d", &n, &m);21         f = 0;22         ma = 0;23         CLR(du, 0);24         for(i = 1; i<= n; ++i)25             scanf("%d", &a[i]);26         for(i = 1; i <= m; ++i){27             scanf("%d %d", &b, &c);28             du[b]++; du[c]++;29         }30         dd = 0;31         for(i = 1; i <= n; ++i){32             if(du[i]%2) dd++;33         }34         if(dd == 2 || dd==0) f = 1; // 欧拉路的奇度顶点数为 2 或 035         if(!f){printf("Impossible\n");continue;}36         for(i = 1; i<= n; ++i){37             if(((du[i] + 1)/2) %2 == 1)38                 ans ^= a[i];39         }40         if(!dd){//欧拉回路时枚举起点41             for(i = 1; i <= n; ++i){42                 int t = ans ^a[i];43                 ma= max(ma, t);44             }45             ans = ma;46         }47         printf("%d\n", ans);48     }49     return 0;50 }

 

hdu5883(欧拉路)