洛谷 P2731 骑马修栅栏 Riding the Fences &POJ 2230 Watchcow 题解【欧拉路】

作者: wjyyy 分类: 图论,欧拉路,解题报告 发布时间: 2018-07-04 17:28

点击量:9

 

   一个比较坑的就是重边还都要走一遍啊。。。

 

题目背景

Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

题目描述

John是一个与其他农民一样懒的人。他讨厌骑马,因此从来不两次经过一个栅栏。你必须编一个程序,读入栅栏网络的描述,并计算出一条修栅栏的路径,使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马,在任意一个顶点结束。

 

每一个栅栏连接两个顶点,顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。两顶点间可能有多个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

 

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数,那么当存在多组解的情况下,输出500进制表示法中最小的一个 (也就是输出第一位较小的,如果还有多组解,输出第二位较小的,等等)。

 

输入数据保证至少有一个解。

 

输入输出格式

输入格式:

第1行: 一个整数F(1 <= F <= 1024),表示栅栏的数目

 

第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。

 

输出格式:

输出应当有F+1行,每行一个整数,依次表示路径经过的顶点号。注意数据可能有多组解,但是只有上面题目要求的那一组解是认为正确的。

 

输入输出样例

输入样例#1:
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
 
输出样例#1:
1
2
3
4
2
5
4
6
5
7
 

说明

题目翻译来自NOCOW。

 

解法:

   首先介绍一下欧拉路,欧拉路就是把图上的所有边恰好遍历一遍的路线。我们需要求出这个欧拉路,这个题可能有重边和自环,并且要求输出字典序最小的答案。

 

   为了构造字典序最小,我们首先把所有边都读入进来,包括重边和自环。接着我们把这些边按编号较小的点为第一关键字,编号较大的点为第二关键字,插入链表。注意是链表,而前向星要从大往小插入。

 

   在找欧拉路时,就可以直接按链表顺序dfs所有的边,并且我们可以做一个优化。就是遍历到一个可dfs的点,把当前链表指针存起来,或者直接把head指向这个指针,这样就可以把原来最坏复杂度为\(O(nm)\)的算法优化到\(O(n+m)\)了。每次做完dfs把指向的点入栈,最后把栈输出就是欧拉路了。

 

    核心:找欧拉路的方法:判断是否入度为奇数的点只有不超过2个。任意找一个度为1的出发点(本题要求最小),如果没有度为1的,就任取一个。遍历没有遍历过的边,调用dfs函数,dfs结束后将这个点入栈,如果某个点多次入栈说明它连接了至少一个环,这样栈里面就是欧拉路了,原理可以看《算法竞赛进阶指南》的详细解释。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
using std::sort;
struct edge
{
    int x,y;
    friend bool operator <(edge a,edge b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
}e[25100];
struct node
{
    int n;
    bool used;
    node *nxt,*op;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
        op=NULL;
        used=false;
    }
    node()
    {
        nxt=NULL;
        op=NULL;
        used=false;
    }
};
node head[510],*tail[510];
int deg[510];
int S[25100],top=0;
void dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!p->used)
        {
            head[x]=*p;//修改当前做到的“光标”
            p->used=true;
            p->op->used=true;
            dfs(p->n);
            S[++top]=p->n;//入栈
            p=&head[x];//继续做时要移动“光标”
        }
    }
}
int main()
{
    memset(deg,0,sizeof(deg));
    for(int i=1;i<=500;i++)
        tail[i]=&head[i];
    int m,u,v;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        e[i].x=min(u,v);//保证小的在前
        e[i].y=max(u,v);
        deg[u]++;
        deg[v]++;
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        tail[e[i].x]->nxt=new node(e[i].y);//排序
        tail[e[i].x]=tail[e[i].x]->nxt;
        tail[e[i].y]->nxt=new node(e[i].x);
        tail[e[i].y]=tail[e[i].y]->nxt;
        tail[e[i].x]->op=tail[e[i].y];
        tail[e[i].y]->op=tail[e[i].x];
    }
    int flag=0,s;
    for(int i=1;i<=500;i++)
        if(deg[i]&1)
        {
            s=i;
            flag=1;
            break;
        }
    if(flag==0)
    {
        dfs(1);
        S[++top]=1;
    }
    else
    {
        dfs(s);
        S[++top]=s;
    }
    while(top)
        printf("%d\n",S[top--]);
    return 0;
}

 

POJ2230

   与这题类似,都是找欧拉路,不过这题表示存在欧拉回路,就是起点和终点都是同一个点(题目中为1),要求所有点的度数都为偶数。不过双向图一定存在欧拉回路就是了,双向图都要各走一遍,题目有SPJ就不需要注意太多的细节。

 

Code:

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt;
    bool used;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
        used=false;
    }
    edge()
    {
        nxt=-1;
        used=false;
    }
}e[105555];
int head[10100],cnt=-1;
void add(int from,int to)
{
    e[++cnt]=edge(to,head[from]);
    head[from]=cnt;
}
int cur[10100];
int S[105555],top=0;
void dfs(int x)
{
    for(int i=cur[x];~i;i=e[i].nxt)
    {
        if(!e[i].used)
        {
            e[i].used=true;
            cur[x]=e[i].nxt;//调整光标
            dfs(e[i].n);
            S[++top]=e[i].n;
        }
    }
}
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    int flag=0,s=1;
    for(int i=1;i<=n;i++)
        cur[i]=head[i];
    dfs(1);
    S[++top]=1;
    for(int i=top;i;i--)
        printf("%d\n",S[i]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */