1124. 骑马修栅栏(欧拉路径,模板)
农民John每年有很多栅栏要修理。
他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个与其他农民一样懒的人。
他讨厌骑马,因此从来不两次经过一个栅栏。
你必须编一个程序,读入栅栏网络的描述,并计算出一条修栅栏的路径,使每个栅栏都恰好被经过一次。
John能从任何一个顶点(即两个栅栏的交点)开始骑马,在任意一个顶点结束。
每一个栅栏连接两个顶点,顶点用 1 到 500 标号(虽然有的农场并没有 500 个顶点)。
一个顶点上可连接任意多( ≥1 )个栅栏。
所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。
我们如果把输出的路径看成是一个500进制的数,那么当存在多组解的情况下,输出500进制表示法中最小的一个 (也就是输出第一个数较小的,如果还有多组解,输出第二个数较小的,等等)。
输入数据保证至少有一个解。
输入格式
第 1 行:一个整数 F,表示栅栏的数目;
第 2 到 F+1 行:每行两个整数 i,j 表示这条栅栏连接 i 与 j 号顶点。
输出格式
输出应当有 F+1 行,每行一个整数,依次表示路径经过的顶点号。
注意数据可能有多组解,但是只有上面题目要求的那一组解是认为正确的。
数据范围
1≤F≤1024
1≤i,j≤500
输入样例:
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
解析:
求最小字典序的欧拉路径的方法
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 5e2 + 5, M = 2e3, INF = 0x3f3f3f3f;
int n=500,m;
int g[N][N];
int ans[M], cnt;
int d[N];void dfs(int u) {for (int i = 1; i <= n; i++) {if (g[u][i]) {g[u][i]--, g[i][u]--;dfs(i);}}ans[++cnt] = u;
}int main() {cin >> m;for (int i = 1, a, b; i <= m; i++) {cin >> a >> b;g[a][b]++, g[b][a]++;d[a]++, d[b]++;}int s = 1;while (!d[s])s++;for (int i = 1; i <= n; i++) {if (d[i] % 2) {s = i;break;}}dfs(s);for (int i = cnt; i > 0; i--)printf("%d\n", ans[i]);return 0;
}
相关文章:
1124. 骑马修栅栏(欧拉路径,模板)
农民John每年有很多栅栏要修理。 他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。 他讨厌骑马,因此从来不两次经过一个栅栏。 你必须编一个程序,读入栅栏网络的描述,并计算出一条修栅栏的路径…...
C# CAD2016获取数据操作BlockTableRecord、Polyline、DBObject
一、数据操作说明 //DBObject 基础类 DBObject dbObj (DBObject)tr.GetObject(outerId, OpenMode.ForRead); //Polyline 线段类 Polyline outerPolyline (Polyline)tr.GetObject(outerId, OpenMode.ForRead); //BlockTableRecord 块表类 BlockTableRecord modelSpace (Bloc…...
java SSM新闻管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计
一、源码特点 java SSM新闻管理系统是一套完善的web设计系统(系统采用SSM框架进行设计开发,springspringMVCmybatis),对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S…...
Linux_线程
线程与进程 多级页表 线程控制 线程互斥 线程同步 生产者消费者模型 常见概念 下面选取32位系统举例。 一.线程与进程 上图是曾经我们认为进程所占用的资源的集合。 1.1 线程概念 线程是一个执行分支,执行粒度比进程细,调度成本比进程低线程是cpu…...
【selenium】
selenium是一个Web的自动化测试工具,最初是为网站自动化测试而开发的。Selenium可以直接调用浏览器,它支持所有主流的浏览器。其本质是通过驱动浏览器,完成模拟浏览器操作,比如挑战,输入,点击等。 下载与打…...
HX711压力传感器学习一(STM32)
目录 原理图: 引脚介绍: HX711介绍工作原理: 程序讲解: 整套工程: 发送的代码工程,与博客的不一致,如果编译有报错请按照报错和博客进行修改 原理图: 引脚介绍: VCC和GND引…...
作业2.13
1、选择题 1.1、若有定义语句:int a[3][6]; ,按在内存中的存放顺序,a 数组的第10个元素是 D A)a[0][4] B) a[1][3] C)a[0][3] D)a[1][4] 1.2、有数组 int a[5] {10,20,30,40,50},…...
ArcGIS学习(七)图片数据矢量化
ArcGIS学习(七)图片数据矢量化 通过上面几个任务的学习,大家应该已经掌握了ArcGIS的基础操作,并且学习了坐标系和地理数据库这两个非常重要且稍微难一些的专题。从这一任务开始,让我们进入到实战案例板块。 首先进入第一个案例一一图片数据矢量化。 我们在平时的工作学…...
G口大流量服务器选择的关键点有哪些?
G口服务器指的是接入互联网的带宽达到1Gbps以上的服务器,那么选择使用G口大流量服务器的用户需要注意哪些选择 关键点呢?小编为您整理关于G口大流量服务器的关键点。 G口服务器通常被用于需要大带宽支持的业务场景,比如视频流媒体、金融交易平台、电子商…...
MongoDB聚合:$unset
使用$unset阶段可移除文档中的某些字段。从版本4.2开始支持。 语法 移除单个字段,可以直接指定要移除的字段名: { $unset: "<field>" }移除多个字段,可以指定一个要移除字段名的数组: { $unset: [ "<…...
DS Wannabe之5-AM Project: DS 30day int prep day14
Q1. What is Alexnet? Q2. What is VGGNet? Q3. What is VGG16? Q4. What is ResNet? At the ILSVRC 2015, so-called Residual Neural Network (ResNet) by the Kaiming He et al introduced the anovel architecture with “skip connections” and features heavy b…...
【程序设计竞赛】C++与Java的细节优化
必须强调下,以下的任意一种优化,都应该是在本身采用的算法没有任何问题情况下的“锦上添花”,而不是“雪中送炭”。 如果下面的说法存在误导,请专业大佬评论指正 读写优化 C读写优化——解除流绑定 在ACM里,经常出现…...
Java缓冲流——效率提升深度解析
前言 大家好,我是chowley,在我之前的项目中,用到了缓冲流来提高字符流之间的比较速度,缓冲流的主要作用类似于数据库缓存,提高IO操作效率。 缓冲流 在Java的输入输出操作中,缓冲流是提高性能的重要工具之…...
16 亚稳态原理和解决方案
1. 亚稳态原理 亚稳态是指触发器无法在某个规定的时间段内到达一个可以确认的状态。在同步系统中,输入总是与时钟同步,因此寄存器的setup time和hold time是满足的,一般情况下是不会发生亚稳态情况的。在异步信号采集中,由于异步…...
C# OCR识别图片中的文字
1、从NuGet里面安装Spire.OCR 2、安装之后,找到安装路径下,默认生成的packages文件夹,复制该文件夹路径下的 6 个dll文件到程序的根目录 3、调用读取方法 OcrScanner scanner new OcrScanner(); string path "C:\1.png"; scann…...
使用python-numpy实现一个简单神经网络
目录 前言 导入numpy并初始化数据和激活函数 初始化学习率和模型参数 迭代更新模型参数(权重) 小彩蛋 前言 这篇文章,小编带大家使用python-numpy实现一个简单的三层神经网络,不使用pytorch等深度学习框架,来理解…...
CSS定位装饰
网页常见布局方式 标准流 块级元素独占一行---垂直布局 行内元素/行内块元素一行显示多个----水平布局 浮动 可以让原本垂直布局的块级元素变成水平布局 定位 可以让元素自由的摆放在网页的任意位置 一般用于盒子之间的层叠情况 使用定位步骤 设置定位方式 属性名&am…...
java之jvm详解
JVM内存结构 程序计数器 Program Counter Register程序计数器(寄存器) 程序计数器在物理层上是通过寄存器实现的 作用:记住下一条jvm指令的执行地址特点 是线程私有的(每个线程都有属于自己的程序计数器)不会存在内存溢出 虚拟机栈(默认大小为1024kb) 每个线…...
vue3学习——集成sass
安装 pnpm i sass sass-loader -D在vite.config.ts文件配置: export default defineConfig({css: {preprocessorOptions: {scss: {javascriptEnabled: true,additionalData: import "./src/styles/variable.scss";,},},},} }创建三个文件 src/styles/index.scss //…...
开关电源学习之Boost电路
如果我们需要给一个输入电压为5V的芯片供电,而我们只有一个3.3V的电源,那怎么办? 我们能不能把3.3V的电压升到5V? 一、电感的简介 而在升压的电路设计方案中,使用到一个重要的元器件:电感。 电感的特性…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
32单片机——基本定时器
STM32F103有众多的定时器,其中包括2个基本定时器(TIM6和TIM7)、4个通用定时器(TIM2~TIM5)、2个高级控制定时器(TIM1和TIM8),这些定时器彼此完全独立,不共享任何资源 1、定…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
