洛谷 P2731 骑马修栅栏 Riding the Fences &POJ 2230 Watchcow 题解【欧拉路】
点击量：162
一个比较坑的就是重边还都要走一遍啊。。。
题目背景
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：91 22 33 44 24 52 55 65 74 6输出样例#1：1234254657说明
题目翻译来自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;
}
说点什么