2353: 【作】【基础】骑马修栅栏

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：3

题目描述

农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。 

每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。 

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 

输入数据保证至少有一个解。 

输入

第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目  
第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。

输出

输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

样例输入 复制 

9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

样例输出 复制 

1
2
3
4
2
5
4
6
5
7

提示

题目：修栅栏 题目分析

题意简述

农民约翰要修理栅栏，每一段栅栏必须恰好经过一次，不能重复走栅栏（边）。栅栏连接顶点，顶点编号范围 1~500。图是连通无向图。
要求输出一条欧拉路，并且如果有多组解，输出 500 进制最小的那一组（字典序最小路径）。
输入：第一行 F 表示栅栏（边）的数量，后面 F 行每行两个顶点代表一条栅栏；
输出：路径上每个顶点，一个顶点单独占一行。

知识点：无向图欧拉路

无向图欧拉路判定规则：
  1. 图必须连通（题目保证连通，不用写连通判断）
  2. 奇点（度数为奇数的顶点）数量只能是 0 或者 2
    • 奇点数量 = 0：欧拉回路，可以从任意点出发，最后回到起点
    • 奇点数量 = 2：欧拉路径，必须从其中一个奇点出发，另一个奇点结束
本题题目保证至少存在一组解，所以不用处理无解情况。

本题两个核心坑点（也是你刚才测试点没过的原因）

坑 1：存在重边（两个顶点之间可以有多根栅栏）

比如顶点 2 和 5 之间可以同时有 2 根栅栏，代表两条独立的边，都要走一遍。
✅ 解决办法：
邻接矩阵不能只用 0/1 标记有没有边，要存储两点之间边的条数。
每次走过一条边，数量 -1，而不是直接置 0。
旧代码用 0/1，遇到重边会直接丢失多余的边，造成少遍历栅栏，测试点 WA。

坑 2：要求字典序最小（500 进制最小）

题目说明：把整条路径看成 500 进制数字，要最小。等价于优先选择编号更小的顶点走。
✅ 解决办法：
DFS 遍历邻接点时，从小到大依次枚举顶点（i 从 1 到 500），遇到有剩余边的点立刻递归，优先走小编号的点，保证字典序最小。
如果从大到小遍历，得到的路径字典序会偏大，不符合题目要求。

Hierholzer 算法思路（DFS 版，和模板一致）

  1. 建图：邻接矩阵记录边的数量，同时统计每个点的度数。
  2. 选择起点：
    • 从小到大遍历顶点，找到第一个奇点作为起点；
    • 如果没有奇点（全偶度），起点选编号最小顶点。
  3. DFS 递归：
    从当前点x，从小到大遍历所有顶点i，只要x和i之间还有边：
    • 消耗一条边：a[x][i]--、a[i][x]--
    • 递归访问 i
    ⚠️ 关键点：回溯的时候才把点加入路径数组，而不是进函数立刻记录
  4. 输出：
    DFS 结束后，得到的路径数组是逆序的，倒序输出数组，每个顶点单独一行，就是答案。

输入输出要点

  • 输入：只有边数 F，没有顶点总数 n，顶点最大编号 500。
  • 输出：路径一共有 F+1 个顶点，每行输出一个数字，不能空格隔开。 

#include <bits/stdc++.h>
using namespace std;
int a[505][505];//邻接矩阵：存两点之间边的数量（支持重边！）
int d[505];//存储每个结点的度
int r[2000];//存储走过的点，最多1024条边，路径长度1025
int k = 0;//表示数组长度

//从 x 深搜
void dfs(int x){
    //从小到大枚举i！保证字典序最小（关键）
    for(int i = 1;i <= 500;i++){
        //只要还有边
        if(a[x][i] > 0){
            //拆掉这一条边，重边就数量-1，不是直接置0
            a[x][i] --;
            a[i][x] --;
            dfs(i);
        }
    }
    //回溯时，记录路径
    k++;
    r[k] = x;
}
int main(){
    int e;
    cin>>e;//e就是栅栏数量F
    int x,y;
    memset(a,0,sizeof(a));
    memset(d,0,sizeof(d));
    //读入 e 条边
    for(int i = 1;i <= e;i++){
        cin>>x>>y;
        a[x][y]++;
        a[y][x]++;
        //统计结点的度
        d[x]++;
        d[y]++;
    }
    //求起点：从小到大找奇点；无奇点则起点为最小点
    int s = 1;
    for(int i = 1;i <= 500;i++){
        if(d[i] % 2 == 1){
            s = i;
            break;
        }
    }
    dfs(s);//从 s 开始搜索
    //逆序打印欧拉路，每个数字单独一行
    for(int i = k;i >= 1;i--){
        cout<<r[i]<<endl;
    }
    return 0;
}

来源/分类

提交提交记录统计露一手!