UVA302 John's trip 题解

· · 题解

UVA302 John's trip

给定一张图和起点，求从起点开始能否把每条边遍历一次后返回起点，并输出字典序最小的路径。

欧拉回路裸题，若可以达到题目的要求，则图中必然存在一条欧拉回路。我们可以记录每个点的连的边数，如果出现一个点连的边数为奇数，那么图中必定不存在欧拉回路，输出 Round trip does not exist. 即可。原因是如果存在欧拉回路，那么回到起点前，走到每个点时必定还有一条路离开。所以走到一个点是一条路，离开一个点又是一条路，合起来就是两条路。如果一个点被经过两次，那么就是四条路。易得欧拉回路中每个点连的边数为偶数。

然后，对于存在欧拉回路的情况，我们可以从起点出发进行 DFS。由于题目要求输出字典序最小的路径，所以我们先遍历编号小的边。参照输出经过的点的路径的做法，当一条边遍历完成之后，将其压入栈中，最后倒序输出。

注意，这里有一个小坑点：如果一条边在遍历中走过了，由于每一条边只能经过一次，所以就不能再走了，这点和输出经过的点的路径不一样。所以，在走边都时候要注意判断这条边已经走过没有，否则会得到错误结果。

另外，再重复一遍翻译里的话：每次输出完额外换一行！

#include <bits/stdc++.h>
using namespace std;
struct egde
{
    int v,next,d;
}e[30000];
struct edgein
{
    int d,t;
};
int n,m,b,d[30000],h[30000],lu[60000],book[30000],cnt=0,tol=0;
bool cmp(struct edgein a,struct edgein b)
{
    return a.d<b.d;
}

void add_edge(int u,int v,int d)
{
    e[++tol].next=h[u];
    e[tol].v=v;
    e[tol].d=d;
    h[u]=tol;
}

void dfs(int now)
{
    int cn=0;
    struct edgein s[2000];
    for(int i=h[now];i;i=e[i].next)
        if(!book[e[i].d])s[++cn].d=e[i].d,s[cn].t=e[i].v;
    if(cn==0)return;
    sort(s+1,s+cn+1,cmp);
    for(int i=1;i<=cn;i++)
        if(!book[s[i].d])
            {
            int k=s[i].d;
            book[s[i].d]=1;
            dfs(s[i].t);
            lu[++cnt]=k;
            }
}

int main()
{
    int u=0,v=0;
    while(scanf("%d%d",&u,&v)!=-1)
        {
        if(u==0&&v==0)break;
        int flag1=1,flag2=0,flag3=0;
        scanf("%d",&b);
        n=max(n,max(u,v));m=min(u,v);
        d[u]++;d[v]++;
        add_edge(u,v,b);add_edge(v,u,b);
        while(scanf("%d%d",&u,&v)!=-1)
            {
                if(u==0&&v==0)break;
                scanf("%d",&b);
                n=max(n,max(u,v));
                d[u]++;d[v]++;
                add_edge(u,v,b);add_edge(v,u,b);
            }
        for(int i=1;i<=n;i++)
            {
            if(d[i]%2)flag3=1,flag1++;
            else if(d[i]%2&&i==m)flag2=1;
            }
        flag1=(flag1<=2)&&(!(flag2^flag3));
        if(flag1)
            {
            dfs(m);
            for(int i=cnt;i>0;i--)
                if(i!=1)printf("%d ",lu[i]);
                else printf("%d",lu[i]);
            printf("\n\n");    
            }
        else printf("Round trip does not exist.\n\n");
        cnt=0;tol=0;
        memset(h,0,sizeof(h));memset(lu,0,sizeof(lu));memset(d,0,sizeof(d));
        memset(book,0,sizeof(book));
        }
    return 0;
}

AC记录