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? 一、电感的简介 而在升压的电路设计方案中,使用到一个重要的元器件:电感。 电感的特性…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
