信息学奥赛一本通 1375：骑马修栅栏(fence) | 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences-Toy模板网

这篇具有很好参考价值的文章主要介绍了信息学奥赛一本通 1375：骑马修栅栏(fence) | 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【题目链接】

ybt 1375：骑马修栅栏(fence)
洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences

【题目考点】

1. 图论：欧拉回路

欧拉回路存在的条件：图中所有顶点的度都是偶数
欧拉路径存在的条件：图中只有两个度为奇数的顶点。而且这两个顶点是欧拉路径的起点与终点。

求解欧拉回路使用Hierholzer算法
复杂度： $O (V + E)$

【解题思路】

该图是无向图，顶点就是图中的顶点，栅栏是边。
“栅栏都是连通的”，意味着这是一个无向连通图。
“使每个栅栏都恰好被经过一次”，就是每条边都经过一次。该问题为求欧拉路径。可以使用Hierholzer算法解决。
“两顶点间可能有多个栅栏”意味着可能有重边，但Hierholzer算法可以处理有重边或自环的图。
“输出500进制表示法中最小的一个”，即为输出字典序最小的欧拉路径顶点序列。
只需要在实现Hierholzer算法时，包括选择起始顶点或某顶点的邻接点时，尽量选择编号较小的顶点来访问即可。

在输入边时，统计顶点编号的最大值，作为总顶点数量。

首先从小到大遍历所有顶点

如果存在奇数度的顶点，选择该顶点作为起始点。
如果不存在奇数度的顶点，那么所有顶点的度都是偶数，任选顶点作为起始点。这里选择1号顶点为起始点。

从起始顶点出发，进行深搜，使用Hierholzer算法求欧拉路径。为了满足条件，必须按顶点编号从小到大访问一个顶点的所有邻接点。

可以使用邻接矩阵或邻接表完成该题。文章来源地址https://www.toymoban.com/news/detail-477713.html

【题解代码】

解法1：邻接矩阵

#include<bits/stdc++.h>
using namespace std;
#define N 505
int edge[N][N], n, m, deg[N];//n:顶点数 m:边数 deg[i]:顶点i的度
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{
    for(int v = 1; v <= n; ++v)
    {
        if(edge[u][v])
        {
            edge[u][v]--;
            edge[v][u]--;
            dfs(v);
        }
    }
    stk.push(u);
}
int main()
{
    int f, t, st = 1;//st:起点 
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        n = max(n, max(f, t));
        edge[f][t]++;
        edge[t][f]++;
        deg[f]++;
        deg[t]++;
    }
    for(int v = 1; v <= n; ++v)//如果找到奇数度顶点，就从奇数度顶点出发，否则从1出发 
    {
        if(deg[v] % 2 == 1)
        {
            st = v;
            break;
        }
    }
    dfs(st);
    while(stk.empty() == false)
    {
        cout << stk.top() << endl;
        stk.pop();
    }
    return 0;
}

解法2：邻接表

#include<bits/stdc++.h>
using namespace std;
#define N 505
#define M 1050
struct Node
{
	int v, e;//v：顶点 e：边编号 
	Node(){}
	Node(int a, int b):v(a), e(b){}
};
int n, m, beg[N], deg[N];//n:顶点数 m:边数 deg[i]:顶点i的度 beg[i]:顶点i的邻接点从edge[i][beg[i]]开始 
bool vis[M];//vis[i]：边i是否已访问过 
vector<Node> g[N];
stack<int> stk;
bool cmp(Node a, Node b)
{
	return a.v < b.v;
}
void dfs(int u)//Hierholzer算法 
{
    for(int &i = beg[u]; i < g[u].size(); ++i)
    {
    	int v = g[u][i].v, e = g[u][i].e;
        if(vis[e] == false)
        {
            vis[e] = true;
            dfs(v);
        }
    }
    stk.push(u);
}
int main()
{
    int f, t, st = 1;//st:起点 
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        n = max(n, max(f, t));
        g[f].push_back(Node(t, i));
        g[t].push_back(Node(f, i));
        deg[f]++;
        deg[t]++;
    }
    for(int v = 1; v <= n; ++v)
    	sort(g[v].begin(), g[v].end(), cmp);
    for(int v = 1; v <= n; ++v)
    {//如果找到奇数度顶点，就从奇数度顶点出发，否则从1出发 
        if(deg[v] % 2 == 1)
        {
            st = v;
            break;
        }
    }
    dfs(st);
    while(stk.empty() == false)
    {
        cout << stk.top() << endl;
        stk.pop();
    }
    return 0;
}