当前位置: 首页 > news >正文

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

【题目链接】

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

【题目考点】

1. 图论:欧拉回路

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

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

【解题思路】

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

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

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

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

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

可以使用邻接矩阵或邻接表完成该题。

【题解代码】

解法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;
}

相关文章:

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

【题目链接】 ybt 1375&#xff1a;骑马修栅栏(fence) 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences 【题目考点】 1. 图论&#xff1a;欧拉回路 欧拉回路存在的条件&#xff1a;图中所有顶点的度都是偶数欧拉路径存在的条件&#xff1a;图中只有两个度为奇数的顶点…...

Spring Boot 应用的打包和发布

1. 创建项目&#xff08;example-fast&#xff09; 基于 Spring Boot 创建一个 WEB 项目 example-fast。 2. 编译打包 2.1 采用 IDEA 集成的 Maven 环境来对 Spring Boot 项目编译打包&#xff0c;可谓是超级 easy 2.2 mvn 命令打包 # mvn clean 清理编译 # install 打包 #…...

linux:iptables (3) 命令行操练(一)

目录 1.命令行手册查缺补漏 2.开始练习,从最陌生的参数练习开启 2.1 --list-rules -S &#xff1a;打印链或所有链中的规则 2.2 --zero -Z 链或所有链中的零计数器 2.3 --policy -P 修改默认链的默认规则 2.4 --new -N 接下来练习添加和删除自定义链 1.命令行手册查缺补…...

synchronized(this) 与synchronized(class) 有啥区别

前言 synchronized(this) 与 synchronized(class) 相同处&#xff1a;均对代码加锁&#xff0c;实现互斥性。synchronized(this) 与 synchronized(class) 区别&#xff1a;作用域不同。 synchronized (this) synchronized(this)使用的是对象锁。this为关键词&#xff0c;表示…...

BOSS直拒、失联招聘,消失的“金三银四”,失业的测试人出路在哪里?

裁员潮涌&#xff0c;经济严冬。最近很多测试人过得并不好&#xff0c;行业缩水对测试岗位影响很直接干脆&#xff0c;究其原因还是测试门槛在IT行业较低&#xff0c;同质化测试人员比较多。但实际上成为一位好测试却有着较高的门槛&#xff0c;一名优秀的测试应当对产品的深层…...

华为OD机试【密室逃生游戏】

密室逃生游戏 题目 小强增在参加《密室逃生》游戏&#xff0c;当前关卡要求找到符合给定 密码 K&#xff08;升序的不重复小写字母组 成&#xff09; 的箱子&#xff0c; 并给出箱子编号&#xff0c;箱子编号为 1~N 。 每个箱子中都有一个 字符串 s &#xff0c;字符串由大写字…...

【Python学习笔记(六)】json解析模块的使用

json解析模块的使用 前言 json 是一种轻量级的数据交换格式&#xff0c;通过对象和数组的组合来表示数据。在 Python3 中可以使用 json 模块来对 json 数据进行编解码。 json 模块 是 Python 标准库模块&#xff0c;无需手动安装&#xff0c;可以直接导入 import json # 导入…...

《Spring系列》第3章 基于注解管理Bean

基于注解方式管理Bean 1.通过注解管理Bean 1) 基础注解 Component Service Controller Repository 2) 基于XML的注解扫描 a> 引入依赖 spring-aop-5.1.5.RELEASE.jarb> 开启组件扫描 最简单的开启注解 <context:component-scan base-package"com.jianan&q…...

【Redis】十大数据类型(下篇)

文章目录redis位图(bitmap) --- 底子还是string基本命令图示setbit key offset value setbit 键 偏移位 只能零或者1getbit key offset 查看获取字符串长度 strlen统计key中包含1的个数 bitcount keybitop 统计两个比特key是否都为1技术落地&#xff1a;打卡签到&#xff0c;频…...

【第十一届“泰迪杯”数据挖掘挑战赛】B题产品订单的数据分析与需求预测“解题思路“”以及“代码分享”

【第十一届泰迪杯B题产品订单的数据分析与需求预测产品订单的数据分析与需求预测 】第一大问代码分享&#xff08;后续更新LSTMinformer多元预测多变量模型&#xff09; PS: 代码全写有注释&#xff0c;通俗易懂&#xff0c;包看懂&#xff01;&#xff01;&#xff01;&…...

Python入门到高级【第一章】

预计更新第一章. Python 简介 Python 简介和历史Python 特点和优势安装 Python 第二章. 变量和数据类型 变量和标识符基本数据类型&#xff1a;数字、字符串、布尔值等字符串操作列表、元组和字典 第三章. 控制语句和函数 分支结构&#xff1a;if/else 语句循环结构&#…...

【泰凌微TLSR8258 zigbee】OTA升级操作方法

目录 程序启动模式多地址启动模式Bootloader 启动模式多地址启动模式 Flash 分布Bootloader 启动模式Flash分布模式OTA升级OTA初始化OTA ServerOTA ClientOTA升级固件生成程序启动模式 在介绍OTA升级操作方法前,我们先介绍一下程序的启动模式,以及不同启动模式的优缺点。 多…...

网络基础设施监控

在过去的几十年里&#xff0c;网络基础设施在规模和功能方面都变得复杂起来。不断增长的业务需求和不断增长的技术能力推动了这种快速增长&#xff0c;监控网络基础设施以确保其最佳性能和最大效率已成为任何希望成为行业领跑者的组织不可或缺的优先事项。 什么是网络基础设施…...

OPNET Modeler 例程——创建一个包交换网络

文章目录一、例程简介二、创建新的包格式三、创建新的链路模型四、创建中心交换节点模型五、创建中心交换节点的进程模型六、创建周边节点模型七、创建周边节点进程模块八、创建网络模型九、收集统计量十、配置并仿真总结一、例程简介 本例程将仿真一个简单的包交换网络&#…...

JSON 基础结构

什么是JSON JSON&#xff0c;说白了就是JavaScript用来处理数据的一种格式&#xff0c;这种格式非常简单易用。 JSON&#xff0c;大部分都是用来处理JavaScript和web服务器端之间的数据交换&#xff0c;把后台web服务器的数据传递到前台&#xff0c;然后使用JavaScript进行处…...

雷达基础知识

雷达频率划分 以下是按照频率和波长划分雷达频段的表格&#xff1a; 波段名称频率范围&#xff08;GHz&#xff09;波长范围&#xff08;cm&#xff09;应用领域VHF0.03 - 0.3100 - 10气象雷达、空管雷达、航空雷达UHF0.3 - 3100 - 10航空雷达、海上雷达、地面雷达、火控雷达…...

【二阶锥规划】考虑气电联合需求响应的气电综合能源配网系统协调优化运行【IEEE33节点】(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

qt 编译器 调试器

电脑版本&#xff1a;win10 64位 qt版本&#xff1a;based on Qt 5.14.0&#xff08;msvc 2017&#xff0c; 32位&#xff09; Qt Creator 4.11.0 qt安装包&#xff1a;qt-opensource-windows-x86-5.9.9.exe 安装过程一路next&#xff0c;安装完成后&#xff0c;默认使用的…...

低代码平台助力AIGC:让人工智能技术更加普及和高效

今年人工智能的风是吹了一波又一波&#xff0c;从ChatGPT到文心一言&#xff0c;短短四个多月的时间&#xff0c;GPT完成了从3.0、3.5到4.0的推新发布&#xff0c;一步步刷新了民众对于目前人工智能技术发展的认知底线&#xff0c;让人们直观地感受到了人工智能技术的蓬勃发展。…...

Qt中Model/View结构

Qt中Model/View结构 Model/View框架的核心思想是模型&#xff08;数据&#xff09;与视图&#xff08;显示&#xff09;相分离&#xff0c;模型对外提供标准接口存取数据&#xff0c;不关心数据如何显示&#xff0c;视图自定义数据的显示方式&#xff0c;不关心数据如何组织存…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...