P2731

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

题目背景

Farmer John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

题目描述

John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。

John 的农场上一共有 $m$ 个栅栏，每一个栅栏连接两个顶点，顶点用 $1$ 到 $500$ 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 $1$ 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。

你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 $500$ 进制的数，那么当存在多组解的情况下，输出 $500$ 进制表示法中最小的一个（也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。

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

输入格式

第一行一个整数 $m$ ，表示栅栏的数目。

从第二行到第 $(m+1)$ 行，每行两个整数 $u,v$ ，表示有一条栅栏连接 $u,v$ 两个点。

输出格式

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

数据保证至少有一组可行解。

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

对于 $100\%$ 的数据， $1 \leq m \leq 1024,1 \leq u,v \leq 500$ 。

题目翻译来自NOCOW。

USACO Training Section 3.3

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences 题解 Author: Yuyi 题目分析与推导过程这道题和之前的《P7771 欧拉路径》可以说是“同源兄弟”，只不过这一次我们的图变成了无向图（且存在重边），要求输出的同样是字典序最小的欧拉路径。判定无向图欧拉路径的起点规则：在无向图中，我们不需要分别统计入度和出度，…

点击展开完整题解点击收起题解

2026年8月10日 20:29

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences 题解

Author: Yuyi

题目分析与推导过程

这道题和之前的《P7771 欧拉路径》可以说是“同源兄弟”，只不过这一次我们的图变成了无向图（且存在重边），要求输出的同样是字典序最小的欧拉路径。

判定无向图欧拉路径的起点规则： 在无向图中，我们不需要分别统计入度和出度，只需要统计每个点的总度数（连接的边数）。根据欧拉路径的定理：

如果所有顶点的度数都是偶数：说明图中存在欧拉回路（从任意一点出发都能走回原点）。为了让字典序最小，我们应当从所有有边的顶点中，编号最小的那个点出发。
如果恰好有两个顶点的度数是奇数：说明图中存在欧拉通路，且这两个奇数度数的点必定一个是起点，一个是终点（除此之外的其他点度数必须全为偶数）。为了让字典序最小，我们应当从这两个奇数点中编号较小的那个点出发。

（由于题目大方地保证了“至少有一个解”，所以我们不需要像上一题那样去额外写无解的特判了。）

字典序与存图的小窍门： 因为题目的顶点编号极小（ $1 \leq u,v \leq 500$ ），比起用 vector 存图然后再进行 sort 排序，我们可以直接使用一个二维数组（邻接矩阵） G[u][v] 来记录 $u$ 到 $v$ 的连边数量！这有两个极其巨大的好处：

自动排序：我们在 DFS 枚举下一个点时，直接 rep(v,1,500) 从小到大遍历。如果 G[u][v] > 0，就直接走过去。这天生就完美契合了“字典序最小”的贪心要求，连 sort 都省了！
极致简单的删边：因为这是无向图，如果用边表存图，往往需要成对删除正反向边（用异或建边法 i 和 i^1）。但在这里一旦走了某条边，直接粗暴地 G[u][v]--; G[v][u]--; 即可，重边问题也迎刃而解。

最后，和有向图一样，利用 Hierholzer 算法，当我们 DFS 深入到一个点，发现它周围的边已经全部走完，无路可走时，就把这个点丢进答案栈里。最终逆序输出这个栈，就是我们要的欧拉路径。

正解代码

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 505;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int m;
// G[u][v] 记录点 u 到点 v 之间有几条边，直接充当邻接矩阵，完美解决重边问题
int G[maxn][maxn];
int deg[maxn];
int ans[2005],cnt;

void dfs(int u)
{
    // 从 1 到 500 顺次遍历，天生满足字典序最小的贪心策略
    rep(v,1,500)
    {
        if(G[u][v] > 0)
        {
            // 无向图删边，双向同时减一
            G[u][v]--;
            G[v][u]--;
            dfs(v);
        }
    }
    // 无路可走时，将当前点压入答案栈
    ans[++cnt] = u;
}

void solve()
{
    read(m);
    int start_node = 505;
    rep(i,1,m)
    {
        int u,v;
        read(u),read(v);
        G[u][v]++;
        G[v][u]++;
        deg[u]++;
        deg[v]++;
        // 顺手记录一下出现过的最小编号节点，以防是全偶数的欧拉回路
        start_node = min({start_node, u, v});
    }
    
    int S = 0;
    // 寻找奇数度数的点
    rep(i,1,500)
    {
        if(deg[i] % 2 == 1)
        {
            if(S == 0) S = i; // 找到的第一个奇数度数点必定是编号最小的奇数点，直接作为起点
            // 因为是从 1 开始正向遍历，找到即可，无需继续比较大小
        }
    }
    
    // 如果没有奇数度数的点，说明是欧拉回路，从有边的、编号最小的点出发
    if(S == 0) S = start_node;
    
    dfs(S);
    
    // 答案逆序输出，且题目要求一行一个数字
    dep(i,cnt,1) cout << ans[i] << '\n';
    return;
}

int main()
{
    int T_case=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T_case);
    while(T_case--) solve();
    return 0;
}

Generated by Gemini 3.1 Pro

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。