欧拉图

HDU 5883 2016 ICPC青岛网络赛

坑爹啊!!!!!!!当时这道题想了我好久好久 想到各种歪的地方 到最后没有一个地方是想对的 都是想多的 日
怎么说呢 一眼看出是欧拉图问题 但是一开始没想起 异或运算的规则 傻傻的把欧拉路径的算法给敲了一直超时
//顺便稍微写一下异或运算的性质好了 1. 两个相同的数异或得 0 2.0与任意一个数异或 则这个数不变 3. 多个数异或与顺序无关
回归正题 关于欧拉图的性质 简单回顾一下
欧拉通路 所有结点连通并且只有两个结点的 度 为奇数
欧拉回路 所有结点连通并且所有结点的 度 为偶数
另外 欧拉通路的起点和终点固定 欧拉回路的起点(也是终点)任意
这样就可以写了 比完之后关注了一下这道题的博客 感觉他们还是有些逻辑漏洞 然而他们还是A了

AC code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;
const int maxn=100010;
int n,m;
int val[maxn],root[maxn],degree[maxn],sum[maxn];
bool vis[maxn];

void init()
{
    for(int i=0;i<=n;i++)
    {
        root[i]=i;
        degree[i]=1;//这里把所有节点的度数初始化1   这样就  最后的度数是否为奇数的判断可以省略
        sum[i]=1;//这个图上的连通节点
        vis[i]=true;//初始化设置为true
    }
}

int fin(int x)
{
    return root[x]==x?x:(root[x]=fin(root[x]));
}

int main()
{
    int test,u,v,ru,rv;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d",&n,&m);
        init();
        for(int i=1;i<=n;i++) scanf("%d",val+i);
        while(m--)
        {
            scanf("%d %d",&u,&v);
            degree[u]++;
            degree[v]++;
            ru=fin(u);
            rv=fin(v);
            if(ru!=rv)
            {
                root[ru]=rv;
                sum[rv]+=sum[ru];
            }
        }
        int num=0,ans=0,tmp=0,ri,key=1;
        for(int i=1;i<=n;i++)
            if(degree[i]%2==0) num++;  //因为之前把所有节点的  度  初始化为 1    所以这里的判断改成偶数
        for(int i=1;i<=n;i++)
        {
            ri=fin(i);
            if(ri!=i)
            {
                key=ri;//找到一个连通图   并记录其根节点
                break;
            }
        }
        for(int i=1;i<=n;i++)
            if(fin(i)==i)//对于孤立的节点进行排除
            {
                tmp++;
                vis[i]=false;
            }
        vis[key]=true;
        if(sum[key]+tmp-1!=n||(num!=0&&num!=2))//如果连通图的节点数+孤立点的数目不等于总节点数 那么 必然有另一个连通图 此时必然走不完 
                                               //或者不满足欧拉条件 节点度数为奇数(这里为偶数)的个数
        {
            puts("Impossible");
            continue;
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]) continue;
            if(degree[i]/2%2)//如果经过这个节点有奇数次   则对其进行异或
                ans^=val[i];
        }
        if(num==0)//如果是欧拉回路   那么起点(终点)是任意的   最后再对连通图内的所有节点比较一下
            for(int i=1,tmp=ans;i<=n;i++)  
                if(vis[fin(i)]) ans=max(ans,tmp^val[i]);  
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注