

下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、WC2007模拟题 命题人 顾研第4页 共4页道路规划road【问题描述】Henryy国这一块广大而富庶的土地不断对Henryy国的一代一代新人提出新的挑战。在思想与行动上代代子民都勇于面对挑战,也因而造就国家的进步。当高山挡住去路,Henryy国人就绕道或穿凿高山,建造公路和铁路;洪水威胁时,Henryy国人建造水坝与堤防遏阻水势;在干旱地区,Henryy国人建造伟大的灌溉系统。为了骋驰于广大的田野中,Henryy国人更开创了庞大的运输系统以及通讯系统。在Henryy国有n个城市,m条宽敞的双向高速公路使任意两座城市都可相互达到。然而很不幸Henryy国是个地震频发的国家。一次强烈的地震完全
2、可以使得某条高速公路中断通行能力,因此有可能使两个城市不能互达。而且你也清楚,维修道路是一件费时费力的事情,这也阻碍了Henryy随时巡游。作为Henryy国的交通局局长,现在必须确定通过修最少的一些道路来为Henryy解决这个问题,使得无论那一条道路被破坏,任意两个城市依然能互达。【输入文件】第一行两个整数n,m。接下来m行,每行两个整数a和b(1a,bn),表示a与b之间有一条高速公路。【输出文件】第一行一个整数k,表示最少需要新修道路的条数。接下来k行,描述每条你要新修的路连接的城市的编号。【样例输入】4 31 22 32 4【输出文件】21 41 3【数据约定】3n2500。n-1m2
3、0000。对于30%的数据有3mn11。对于40%的数据有m=4时,不同的连接方法将会导致不同的结果。这是为什么呢?因为像左图,连接了两个叶子合并之后,又产生了一个新的叶子。因此我们添边的时候,首先找到一个叶子,然后开始dfs,直到找到另一个叶子且路径上连出去的非路径边至少为2。把这两个点连边并收缩。重复这一过程,直到叶子数为2或3。会不会不存在这样的连边呢?我们考虑反证法,如果一个叶子到另一个叶子路径上连出去的非路径边为0,则必然只有两个叶子。如果为1,且顺着这个分支走出去的叶子连出去的非路径边也为1,则必然只有3个叶子。在实现方面,由于数据比较小,我们可以不用进行删边、合并的过程,只要标一个号就可以了。这个算法的复杂度是的。在测试中,余林韵同学提出了一种基于dfs遍历的构造方法:如果现在遍历到某个节点A,遍历它的若干个儿子后它有多于2个叶子结点,则把不同的儿子间的叶子
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 甘肃靖远县高三数学试卷
- 高校联盟数学试卷
- 方城县中学二模数学试卷
- 关于千克方面的数学试卷
- 2025年甘肃中医药大学招聘41人笔试历年专业考点(难、易错点)附带答案详解
- 2025至2030船体清洁机器人行业市场深度调研及前景趋势与投资报告
- 赣州高考二模数学试卷
- 二年级毕业题数学试卷
- 高一集合数学试卷
- 体育赛事官方艺术家合作项目的社区参与度分析考核试卷
- GB/T 6075.3-2011机械振动在非旋转部件上测量评价机器的振动第3部分:额定功率大于15 kW额定转速在120 r/min至15 000 r/min之间的在现场测量的工业机器
- GB/T 5594.4-2015电子元器件结构陶瓷材料性能测试方法第4部分:介电常数和介质损耗角正切值测试方法
- GB/T 15558.1-2015燃气用埋地聚乙烯(PE)管道系统第1部分:管材
- GB/T 11060.8-2020天然气含硫化合物的测定第8部分:用紫外荧光光度法测定总硫含量
- 国开专科《外国文学》十年期末考试题库及答案
- 浙江义务教育学校校园饮水质量提升工程建设和维护浙江教育厅
- 林州重机710采煤机电控箱装配流程
- 个人求职简历两页 (46)应聘履历参考模板可编辑修改
- JJF 1847-2020 电子天平校准规范(高清版)
- 统编版小学语二升三衔接阅读专项训练—课外阅读(二)【含答案】
- 积分会员管理系统excel表格模板
评论
0/150
提交评论