算法提高传染病控制_第1页
算法提高传染病控制_第2页
算法提高传染病控制_第3页
全文预览已结束

下载本文档

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

文档简介

1、算法提高 传染病控制时间限制：1.0s内存限制：512.0MB问题描述近来，一种新的传染病肆虐全球。蓬莱国也发现 了零星者，为防止该病在蓬莱国大范围流行，该国决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别携带者，更没有研制出以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断途径的方法控制疾病。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的途径和控制方法已经研究消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有 效的控制办法。问题描述研究表明，这种传染病的具有两种很特殊的性质；第一是它的途径是树型的，一个人 X 只可能被某

2、个特定的人Y，只要Y 不得病，或者是XY 之间的途径被切断，则X 就不会得病。第二是，这种疾病的有周期性，在一个疾病周期之内，传染病将只会一代患者，而不会再给下一代。这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国分易感人群的潜在途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中 心人手不够，同时也缺乏强大的技术，以致他们在一个疾病周期内，的易感人群只能设法切断一条途径，而没有被控制的途径就会引起被（也 就是与当前已经被的人有途径相连，且连接途径没有被切断的人群）。当不可能有健康人被时，疾病就中止。所以，蓬莱国疾控中心要制定出一个 切断途径的顺序，以使尽量少的人被。你的程序要针对给定的树，找出合适的切断顺序。输入格式输入格式的第一行是两个整数 n（1n300）和 p。接下来 p 行，每一行有两个整数i 和j，表示节点i 和j 间有边相连（意即，第i 人和第j 人之间有传播途径相连，注意：可能是i 到j 也可能是j 到i）。其的患者。点 1 是已经被对于给定的输入数据，如果不切断任何途径，

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

温馨提示

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

最新文档

评论

0/150

提交评论