

下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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猪蓝耳病防控及净化指南(第三版)
- TCUWA20059-2022城镇供水管网模型构建与应用技术规程
- 《无人机介绍》课件
- 2025至2030中国压缩空气储能产业现状调查及项目投资策略建议报告
- 三台县2024-2025学年小学六年级数学毕业检测指导卷含解析
- 2025-2030中国硼酸行业市场发展现状及竞争格局与投资研究报告
- 学校中层干部选拔聘用实施方案中层干部选聘实施方案2
- 生物必修1教师用书
- 宅基地互换合同协议书范本
- 2025人教版数学四年级下册 第一单元《四则运算》单元分层作业
- 园艺植物育种学知到课后答案智慧树章节测试答案2025年春浙江大学
评论
0/150
提交评论