信息学集训队作业_第1页
信息学集训队作业_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论