The Best Path(HDU5883)[欧拉路]2016青岛online

xxmlala-fff 2019-09-01 原文

题库链接：http://acm.hdu.edu.cn/showproblem.php?pid=5883

欧拉回路裸题，第一次接触欧拉路的我是真的长见识了^-^

懂了欧拉路这道题就是没什么问题了，欧拉路，指在一个连通图中，一条可以遍历到每条边的路径，按照起点和终点的差异分为欧拉通路（路径的起点和终点不重合）和欧拉回路（路径的起点和终点是同一点）。

1.对于无向连通图，

　　形成欧拉通路的条件：图中的度数为奇数的结点有且仅有两个，其余结点度数均为偶数。

　　形成欧拉回路的条件：图中的每个结点度数为偶数，或者恰好含有两个度数为奇数的结点。

2.对于有向连通图，

　　形成欧拉通路的条件：图中除两个结点外，其余各结点都满足出度等于入度，并且这两个结点中，其中一个出度大于入度，另一个入度大于出度，并且以出度大于入度的点为起点，入度大于出度的点为终点。

　　形成欧拉回路的条件：图中的每个结点出度等于入度

#include<bits/stdc++.h>

using namespace std;

int n,m;
int a[100010],degree[100010];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(degree,0,sizeof(degree));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int u,v;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            degree[u]++;
            degree[v]++;
        }
        int flag=1,tmp=0,num=0;
        int id[2];
        for(int i=1;i<=n;i++){
            if(degree[i]%2){
                flag=0;
                num++;
                if(num<3)
                    id[num-1]=i;
            }
            if((degree[i]/2)&1)
                tmp^=a[i];
        }
        if(!flag&&num!=2)
            cout<<"Impossible\n";
        else {
            int ans=0;
            if(num==0){
                for(int i=1;i<=n;i++){
                    ans=max(ans,tmp^a[i]);
                }
            }
            else ans=tmp^a[id[0]]^a[id[1]];
            cout<<ans<<endl;
        }
    }
    return 0;
}