BZOJ3724 PA2014Final Krolestwo（欧拉回路+构造）

时间：2022-03-16 21:23:35

　　如果没有长度为偶数的限制，新建一个点向所有奇点连边，跑欧拉回路即可，显然此时一定存在欧拉回路，因为所有点度数都为偶数。

　　考虑长度为偶数的限制，将每个点拆成两个点放进一个二分图里，那么每条原图中的边在二分图中会对应两条边，一条长度为偶数的路径在二分图中显然是由某部分出发再走回这部分。我们需要让每条原图中的边恰在二分图中出现一次，且保证所有点度数为偶数，这样仍然跑个欧拉回路就完了。

　　对原图任意取一棵生成树。让非树边任意连，然后通过树边调整度数以达到目的。注意到新建点并连边后，原图中所有点度数都为偶数，而原图中的点在二分图中的对应两点度数之和，就是该点在原图中的度数，也即偶数。也就是说任意点的对应两点度数奇偶性相同，调整一条与其相连的边会同时改变这两点的度数奇偶性。于是考虑怎么调整树边，自底向上，如果某点的儿子当前不满足条件，就改变这条边的连接方式，显然这样儿子的度数就合法了。不断调整上去，最后只剩下根，不过事实上根此时已经合法，因为边的总数是偶数，二分图某边的点度数之和也是偶数，不可能只有根的度数是奇数。

　　悲惨地发现darkbzoj没有spj，那就精神AC吧（感觉浑身是bug）。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

    int x=0,f=1;char c=getchar();

    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

int n,m,p[N],degree[N],dir[N],t=-1;

map<int,int> id[N];

bool flag[N],vis[N];

struct data{int to,nxt;

}edge[N<<1];

void addedge(int x,int y){t++;degree[y]++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

namespace bigraph

{

    int p[N],cur[N],degree[N],stk[N<<1],m=0,top=0,cnt=0,t=-1;

    bool flag[N];

    struct data{int to,nxt;}edge[N<<1];

    void addedge(int x,int y)

    {

        t++;degree[y]++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;

        t++;degree[x]++;edge[t].to=x,edge[t].nxt=p[y],p[y]=t;

        m++;

    }

    void find(int k)

    {

        for (int i=cur[k];~i;i=edge[i].nxt)

        if (!flag[i>>1])

        {

            flag[i>>1]=1;cnt++;

            cur[k]=edge[i].nxt;

            find(edge[i].to);

            if (cnt==m) break;

        }

        stk[++top]=k;

    }

    void print()

    {

        reverse(stk+1,stk+top+1);//for (int i=1;i<=top;i++) cout<<stk[i]<<' ';cout<<endl;

        for (int i=1;i<=top;i++)

        {

            if (i==top) break;

            int x=++i,y;

            for (int j=i+1;j<=top;j++)

            if (stk[j]==0) {y=j-1;break;}

            printf("%d %d %d\n",stk[x],stk[y],y-x);

            for (int j=x;j<y;j++)

            printf("%d ",id[(stk[j]-1)%n+1][(stk[j+1]-1)%n+1]);printf("\n");

            i=y;

        }

    }

}

void dfs(int k)

{

    vis[k]=1;

    for (int i=p[k];~i;i=edge[i].nxt)

    if (!vis[edge[i].to])

    {

        dfs(edge[i].to);

        flag[i>>1]=1;

    }

}

void getdir(int k,int from)

{

    for (int i=p[k];~i;i=edge[i].nxt)

    if (flag[i>>1]&&edge[i].to!=from)

    {

        getdir(edge[i].to,k);

        if (bigraph::degree[edge[i].to]&1) dir[i>>1]=i&1^1;

        else dir[i>>1]=i&1,bigraph::degree[k]^=1;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3724.in","r",stdin);

    freopen("bzoj3724.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();memset(p,255,sizeof(p));

    for (int i=1;i<=m;i++)

    {

        int x=read(),y=read();

        addedge(x,y),addedge(y,x);

        id[x][y]=id[y][x]=i;

    }

    dfs(1);

    for (int i=0;i<t;i+=2) if (!flag[i>>1]) bigraph::degree[edge[i^1].to]^=1;

    for (int i=1;i<=n;i++) if (degree[i]&1) bigraph::degree[i]^=1;

    getdir(1,1);

    memset(bigraph::p,255,sizeof(bigraph::p));

    for (int i=0;i<t;i+=2) bigraph::addedge(edge[i^1].to+dir[i>>1]*n,edge[i].to+(dir[i>>1]^1)*n);

    for (int i=1;i<=n;i++) if (degree[i]&1) bigraph::addedge(0,i);

    memcpy(bigraph::cur,bigraph::p,sizeof(bigraph::cur));

    bigraph::find(0);

    bigraph::print();

    return 0;

}

　　

相关文章