原创problem15巴士路线bus_第1页
原创problem15巴士路线bus_第2页
免费预览已结束，剩余1页可下载查看

下载本文档

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

文档简介

1、巴士路线（bus）提交文件名： bus.pas/c/cpp问题描述：OItown周围有n个小村庄。村庄与村庄之间有公路，每一条公路连接两个村庄。因为这些村庄并不富裕，所以，当初建公路时，这些公路只是恰好将这些村庄连通，也就是说要任意从一个村庄沿着公路走到另一个村庄的方式都是唯一的。于是，有时两个很近的村庄之间要走很长的路。所以，村民们就希望能开通在这些公路上的公共交通路线，方便大家的出行。巴士运营公司采纳了这个意见。同时，巴士公司认为这些巴士线路必须满足下述条件：每条巴士线路的起点和终点都在村庄内，巴士开行的线路都沿着公路；每条公路都要有巴士线路覆盖，这样村民们的出行就只需要换成巴士车就行了；

2、每条公路只被一条巴士线路覆盖，且只被覆盖一次，否则巴士公司觉得在成本上不划算；巴士线路的总数应当最少，这样才能方便管理。例如，如果6个村庄之间的5条公路是这样的：1123456那么这样的3条巴士线路就能满足上面的条件：1-2-3，2-4，5-4-6。不过，居民们自然认为“巴士换乘”是不方便的，因此他们希望从在一个村庄乘车去另一个村庄的路上换乘次数的最大值尽可能少。例如上面这个线路安排中，从村庄1到村庄6需要换成2次，是最大的换乘次数。另一方面，巴士公司认为，一条公交线路越长意味着，如果巴士车发生故障，因此而受影响耽误时间的乘客就越多。所以巴士公司希望，最长的一条线路尽可能短。所谓短，就是途经的

3、村庄少。现在，这个巴士线路设计的任务交给了参加SHTSC的你，你当然要同时考虑上面两方面的因素，所以，你必须先计算出：(1)换乘次数的最大值的最小可能值(2)最长的巴士线路途经的村庄数的最小可能值。输入文件（bus.in）：输入数据的第一行是一个整数n，表示村庄的数目。接下去每行有两个整数x、y，分别描述一条公路，表示村庄x、y之间有一条公路。输入文件保证，每条公路只会被描述一次。输出文件（bus.out）：输出文件有三行。第一行是一个整数，表示巴士线路安排中包含的路线数。第二行是一个整数，表示换乘次数的最大值的最小可能值。第三行是一个整数，表示最长的巴士线路途经的村庄数的最小可能值。输入输出样例：样例一：bus.in61 22 34 54 62 4bus.out323样例二：bus.in121 22 33 44 55 66 72 83 94 105 116 12bus.out623评分如果你的输出的第一行与标准答案相等，你能得2分。如果你的输出的第二行与标准答案相等，你能得4分。如果你的输出的

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论