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

题目分析洛谷P2731要求寻找图中的欧拉路径或欧拉回路并输出字典序最小的路径。欧拉路径指经过图中每一条边恰好一次的路径若起点和终点相同则为欧拉回路。解题思路方法一Hierholzer算法字典序最小路径邻接表建图使用邻接表存储图并通过优先队列或排序保证每次访问最小编号的节点。vectormultisetint 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算法实现递归或迭代方式遍历边并删除已访问的边最后逆序输出路径。stackint stk; vectorint 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; vectormultisetint adj(MAXN); stackint stk; vectorint 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; vectorint 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; }注意事项重边处理使用multiset或邻接矩阵计数避免遗漏重边。字典序保证优先访问编号小的节点可通过排序或优先队列实现。逆序输出Hierholzer算法生成的路径是逆序的需反转后再输出。复杂度分析时间每条边访问一次优先队列维护邻接点。空间存储邻接表和路径。