首页 > 代码库 > hdu_5883_The Best Path(欧拉路)
hdu_5883_The Best Path(欧拉路)
题目链接：hdu_5883_The Best Path
题意：
n 个点 m 条无向边的图，找一个欧拉通路/回路使得这个路径所有结点的异或值最大。
题解：
节点 i 的贡献为（（du[i] +1/ 2) % 2）* a[i]
如果为欧拉回路，需要枚举一下起点，然后取一下最大
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 5 const int N=1e5+7; 6 int t,n,m,du[N],a[N],x,y,ans; 7 8 int T_T(int odd=0,int ans=0) 9 {10 F(i,1,n)if(du[i]&1)odd++;11 if(odd!=0&&odd!=2)return -1;//不存在欧拉路12 F(i,1,n)13 {14 du[i]=(du[i]+1)/2;15 if(du[i]&1)ans^=a[i];16 }17 if(odd==0)F(i,1,n)ans=max(ans,ans^a[i]);//奇度点为0，存在欧拉回路18 return ans;19 }20 21 int main()22 {23 scanf("%d",&t);24 while(t--)25 {26 scanf("%d%d",&n,&m);27 memset(du,0,sizeof(du));28 F(i,1,n)scanf("%d",a+i);29 F(i,1,m)scanf("%d%d",&x,&y),du[x]++,du[y]++;30 if((ans=T_T())==-1)puts("Impossible");else printf("%d\n",ans);31 }32 return 0;33 }
hdu_5883_The Best Path(欧拉路)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。