我的算法书 - [USACO3.3] 骑马修栅栏 Riding the Fences

经典题

栅栏就是边,

问使每个栅栏都恰好被经过一次
输出最小的路径

我们的算法在回溯的时候输出点,这样会得到一条答案路径a->b->c

如果把这个路径反过来,也是一个解c->b->a

最直觉的想法,出发点选最小的

核心在于如何保证路径是最小的:

画个图想一下,可以知道: 每个在dfs上访问的点,都会输出:

a --- b
 \   /
  \ /
   c

我们需要做到两点：

起点最小：如果有多个合法的起点，选择编号最小的那一个。
过程贪心：在 DFS 过程中，当且仅当有多个邻居可以选择时，优先走编号最小的那个邻居。

欧拉路的标准算法（Hierholzer 算法或其 DFS 变体）是回溯时记录路径。

DFS 会一直钻到底，直到无路可走才把点放入栈中。
这意味着：最后访问的点最先入栈，最先访问的点最后入栈。(利用栈倒序的功能)
所以，我们在 DFS 内部按 $1 \to 500$ 的顺序从小到大遍历邻居，这样“小”的邻居会被先递归访问。
最终把栈里的元素弹出来（或者倒序输出数组），就是正确的、字典序最小的顺序。

代码

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

        /**
 * Author by Rainboy blog: https://blog.roj.ac.cn github : https://github.com/rainboylvx
 * date: 2025-12-19 09:45:16
 */
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn];
int g[505][505];
int deg[505];
std::vector<int> path;

void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int u,v;
        std::cin >> u >> v;
        g[u][v]++;
        g[v][u]++;
        deg[u]++;
        deg[v]++;
    }
}

void dfs(int u) {
    // std::cout << u << "\n";
    for(int v = 1;v <= 500 ;++v ) // i: 1->500
    {
        if( g[u][v] > 0) {

            //删除边
            g[u][v] --;
            g[v][u] --;
            dfs(v);
        }
    }
    //回溯的时候加入点
    path.push_back(u);
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    int start_node = -1;
    for(int i = 1;i <= 500 ;++i ) // i: 1->505
    {
        if( deg[i] == 0) continue;

        //记录第一个可行的点
        if(start_node == -1 ) start_node = i;


        if( deg[i] % 2 == 1) 
        {
            start_node = i;
            break;
        }
    }
    dfs(start_node);
    for(int i = path.size()-1;i >=0 ;i--)
    {
        cout << path[i] <<"\n";
    }
    
    return 0;
}

目录

代码