题解：UVA302 John's trip

· · 题解

前置知识

你需要了解欧拉回路、基本图论、搜索，本题输入输出较为恶心，需要有良好的理解能力。

思路讲解

题意很清晰，很多朋友住在不同的街，约翰想走完每条街拜访每一位朋友，每条街只走一次，最后回到起点。

我们把街道看作双向边，给每条边加上编号，路口看作点，要求每条边只走一次且最后回到起点，显然是求出无向图的欧拉回路，知道是求欧拉回路，就很好分析了。

根据欧拉图的性质，每个节点度数一定为偶数，因此我们可以一边建图一边统计度数，接着遍历每个点，若度数不为 0 且为奇数，即非孤点且度数是奇数，就说明无法找到欧拉回路，退出即可。

若该图存在欧拉回路，我们对每个点的边按照编号从小到大排序，实现字典序最小；然后从起点开始搜索，每次取出一条对应点未被标记的边，打上边标记，顺着边连的点继续搜索，搜索结束回溯时将边的编号加入答案栈里；所有搜索结束时，不断输出并弹出栈的栈顶元素，直到为空，这样就完成了求解任务。

代码展示

本题是欧拉回路模板题，但需要注意以下几点：

  1. 多测必须清空。
  2. 行末不允许多余空格。
  3. 每组数据输出的末尾应有两个换行。
  4. 记得给边按照编号大小排序，保证字典序。
  5. 是标记边，并非点。

下面是我的代码，仅供参考：

#include<bits/stdc++.h> 

using namespace std;

#define ll long long
#define ld long double
#define endl '\n'
#define inf 0x3f3f3f3f

int x,y,z,s;
int du[107];

struct edge{
    int to,id;
};
vector<edge> a[107];

bool vis[10007];
stack<int> st;
void dfs(int u){
    for(auto i : a[u]){
        int node=i.to,id=i.id;
        if(vis[id]) continue;
        vis[id]=1;
        dfs(node);
        st.push(id);
    }
}

bool cmp(edge u,edge v){
    return u.id<v.id;
}

int main(){
    while(cin>>x>>y){
        if(x==0&&y==0) return 0;
        memset(vis,0,sizeof vis);
        memset(a,0,sizeof a);
        memset(du,0,sizeof du);

        cin>>z;
        s=min(x,y);
        a[x].push_back({y,z});
        a[y].push_back({x,z});
        du[x]++,du[y]++;

        while(cin>>x>>y){
            if(x==0&&y==0) break;
            cin>>z;
            a[x].push_back({y,z});
            a[y].push_back({x,z});
            du[x]++,du[y]++;
        }

        bool f=0;
        for(int i=1;i<=50;i++){
            if(a[i].size()==0) continue;
            sort(a[i].begin(),a[i].end(),cmp);
            if(du[i]!=0&&du[i]%2==1){
                f=1;
                break;
            }
        }
        if(f){
            cout<<"Round trip does not exist.\n\n";
            continue;
        }

        dfs(s);

        while(!st.empty()){
            cout<<st.top();
            if(st.size()!=1) cout<<" ";
            st.pop();
        }
        cout<<"\n\n";
    }

    return 0;
}