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

jensonljs · 2026-03-07 10:22:15 · 题解

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

思路

欧拉回路板子题。

首先，如果一个点的入度不为偶数，就构不成欧拉回路，输出 Round trip does not exist.。如果能构成欧拉回路，那么就跑 dfs 找欧拉回路，倒序输出边号。

注意点

• 每组数据开始前记得清空数组；
• 注意多组数据的输入；
• 行末无空格。

  AC Code

  #include <bits/stdc++.h>
  using namespace std;
  const int N = 2001;
  vector<pair<int, int>> e[N];
  stack<int> st;
  int x, y, z, S, in[N];
  bool fl, vis[N];
  inline void add(int u, int v, int w) { // 加边
  e[u].push_back({w, v});
  e[v].push_back({w, u});
  ++in[u];
  ++in[v];
  return;
  }
  inline void init() { // 初始化
  for (int i = 1; i <= 44; ++i) e[i].clear();
  memset(in, 0, sizeof in);
  memset(vis, 0, sizeof vis);
  return;
  }
  inline void dfs(int u) { // 深搜找欧拉路径
  for (int i = 0; i < e[u].size(); ++i) {
      int id = e[u][i].first, v = e[u][i].second;
      if (!vis[id]) {
          vis[id] = 1;
          dfs(v);
          st.push(id);
      }
  }
  return;
  }
  inline void solve() {
  init();
  int cnt = 0;
  while (cin >> x >> y) {
      if (x == 0 && y == 0) { // 处理每组数据结束的情况
          if (fl) exit(0);
          fl = 1;
          break;
      }
      if (!cnt) S = min(x, y); // 起点为第一次输入的边中编号小的一个
      ++cnt;
      cin >> z;
      fl = 0;
      add(x, y, z);
  }
  for (int i = 1; i <= 44; ++i) {
      if (in[i] & 1) {
          cout << "Round trip does not exist.\n"; // 不能构成欧拉回路
          return;
      }
  }
  dfs(S);
  while (st.size()) {
      cout << st.top() << (st.size() == 1 ? '\n' : ' '); // 输出欧拉路径
      st.pop();
  }
  return;
  }
  int main() {
  while (1) { // 多组
      solve();
  }
  return 0;
  }