首页 > 代码库 > 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(欧拉路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。