题解：P4038 [CERC 1995] John's Trip

· · 题解

题意

给定一张无向图，求这张图是不是 欧拉图； 如果有解，输出走过街道编号字典序最小的方案。

:::warning[注意]{open}

  1. 行末不得有空格。
  2. 输入一张图结束的标号是 0\;0，输入数据结束再跟一个 0\;0。
  3. 起点是输入第一条街道连接的两个顶点中编号较小的路口处。
  4. 在整个输入数据中，最多有 1995 条街，最多 44 个路口。 :::

思路

这题的实现难点是欧拉回路和 DFS。

对于欧拉回路，只要判断每个结点的度是否均为偶数； 对于 DFS，因为数据小，只要用邻接表存储图（一个结点的邻接表应以连边编号为关键字，对节点进行排序），再普通跑一遍就行了。

主要坑点就是：输入很怪异，输出很坑。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct edge {
    int to, id;
    edge(int t, int i) : to(t), id(i) {}
    // 按边编号从小到大排序，保证字典序最小
    bool operator<(const edge& other) const {
        return id < other.id;
    }
};

const int MAXN = 50;
vector<edge> g[MAXN];
bool vis[2005];
vector<int> ans;
int du[MAXN];

void dfs(int u) {
    for (auto &e : g[u]) {
        int v = e.to;
        int id = e.id;
        if (!vis[id]) {
            vis[id] = true;
            dfs(v);
            ans.push_back(id);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y, z;
    while (cin >> x >> y) {
        if (x == 0 && y == 0) break;
        for (int i = 0; i < MAXN; ++i) {
            g[i].clear();
            du[i] = 0;
        }
        for (int i = 0; i <= 1995; ++i) vis[i] = false;
        ans.clear();
        int st = min(x, y);
        cin >> z;
        g[x].emplace_back(y, z);
        g[y].emplace_back(x, z);
        du[x]++; du[y]++;
        while (cin >> x >> y) {
            if (x == 0 && y == 0) break;
            cin >> z;
            g[x].emplace_back(y, z);
            g[y].emplace_back(x, z);
            du[x]++; du[y]++;
        }
        bool ok = true;
        for (int i = 1; i <= 44; ++i) {
            if (du[i] % 2 != 0) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            cout << "Round trip does not exist.\n";
            continue;
        }
        for (int i = 1; i <= 44; ++i) {
            sort(g[i].begin(), g[i].end());
        }
        dfs(st);
        for (long long i = ans.size() - 1; i >= 1; --i) {
            cout << ans[i] << " ";
        }
        cout << ans[0] << "\n";
    }
    return 0;
}

本体代码写完后经过了 AI 润色。