当前位置：首页 > news >正文

洛谷P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

news 2026/5/27 0:59:29

题目分析

洛谷P2731要求寻找图中的欧拉路径或欧拉回路，并输出字典序最小的路径。欧拉路径指经过图中每一条边恰好一次的路径，若起点和终点相同则为欧拉回路。

解题思路

方法一：Hierholzer算法（字典序最小路径）

邻接表建图
使用邻接表存储图，并通过优先队列或排序保证每次访问最小编号的节点。

vector<multiset<int>> adj(MAXN); // 允许重边 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].insert(v); adj[v].insert(u); }

确定起点
统计每个节点的度数，若存在奇数度节点则选择编号最小的作为起点；否则从编号最小的节点开始。
```
int start = 1; for (int i = 1; i <= n; i++) { if (degree[i] % 2 == 1) { start = i; break; } }
```

Hierholzer算法实现
递归或迭代方式遍历边并删除已访问的边，最后逆序输出路径。

stack<int> stk; vector<int> path; stk.push(start); while (!stk.empty()) { int u = stk.top(); if (!adj[u].empty()) { int v = *adj[u].begin(); stk.push(v); adj[u].erase(adj[u].begin()); adj[v].erase(adj[v].find(u)); } else { path.push_back(u); stk.pop(); } } reverse(path.begin(), path.end());

方法二：回溯法（适用于小规模数据）

暴力枚举路径
通过DFS尝试所有可能的路径，选择字典序最小的合法路径。效率较低，仅适用于边数极少的情况。

方法三：邻接矩阵优化

矩阵标记边
使用邻接矩阵记录边数，每次选择最小编号的邻接点。

int graph[MAXN][MAXN]; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u][v]++; graph[v][u]++; }

路径生成
类似Hierholzer算法，但通过矩阵直接修改边数。

代码实现（完整示例）

#include <bits/stdc++.h> using namespace std; const int MAXN = 505; vector<multiset<int>> adj(MAXN); stack<int> stk; vector<int> path; void hierholzer(int start) { stk.push(start); while (!stk.empty()) { int u = stk.top(); if (!adj[u].empty()) { int v = *adj[u].begin(); stk.push(v); adj[u].erase(adj[u].begin()); adj[v].erase(adj[v].find(u)); } else { path.push_back(u); stk.pop(); } } } int main() { int m; cin >> m; int n = 0; vector<int> degree(MAXN, 0); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].insert(v); adj[v].insert(u); degree[u]++; degree[v]++; n = max({n, u, v}); } int start = 1; for (int i = 1; i <= n; i++) { if (degree[i] % 2 == 1) { start = i; break; } } hierholzer(start); reverse(path.begin(), path.end()); for (int node : path) { cout << node << endl; } return 0; }