首页 > 代码库 > 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