首页 > 代码库 > HDU 5883 The Best Path
HDU 5883 The Best Path
欧拉回路。
首先根据连通性以及欧拉回路存在条件判掉不可能的情况,剩下的情况都存在解。
如果有两个奇度的点,那么答案是唯一的。(可以利用度来求解每一个点被走了几次)
如果全是偶数度的点,那么答案不唯一,但是去掉起点被多访问一次的答案也是唯一的,因此只需枚举起点就可以了。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}}const int maxn=100010;int T,r[maxn],a[maxn],cnt[maxn],n,m;int fa[maxn],sz;int Find(int x){ if(x!=fa[x]) fa[x]=Find(fa[x]); return fa[x];}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); sz=n; memset(cnt,0,sizeof cnt); memset(r,0,sizeof r); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); r[u]++; r[v]++; int fu=Find(u),fv=Find(v); if(fu!=fv) { fa[fu]=fv; sz--; } } if(sz!=1) printf("Impossible\n"); else { int sum=0,p1=-1,p2=-1; for(int i=1;i<=n;i++) { if(r[i]%2==1) { sum++; if(p1==-1) p1=i; else p2=i; } } if(sum!=0&&sum!=2) { printf("Impossible\n"); continue; } int ttt=0; for(int i=1;i<=n;i++) { int xx=(r[i]+1)/2; if(xx%2==0) continue; ttt=ttt^a[i]; } int ans=0; if(sum==2) ans=ttt; else { for(int i=1;i<=n;i++) ans=max(ans,ttt^a[i]); } printf("%d\n",ans); } } return 0;}
HDU 5883 The Best Path
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。