洛谷 P1041 传染病控制 详解

2024-03-15 02:48

本文主要是介绍洛谷 P1041 传染病控制 详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

洛谷 P1041 传染病控制

题目背景

近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是,蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究清楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。

题目描述

研究表明,这种传染病的传播具有两种很特殊的性质;

第一是它的传播途径是树型的,一个人X只可能被某个特定的人Y感染,只要Y不得病,或者是XY之间的传播途径被切断,则X就不会得病。

第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一代患者,而不会再传播给下一代。

这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群的潜在传播途径图(一棵树)。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有传播途径相连,且连接途径没有被切断的人群)。当不可能有健康人被感染时,疾病就中止传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。

你的程序要针对给定的树,找出合适的切断顺序。

输入输出格式

输入格式:

输入格式的第一行是两个整数n(1≤n≤300)和p。接下来p行,每一行有两个整数i和j,表示节点i和j间有边相连(意即,第i人和第j人之间有传播途径相连)。其中节点1是已经被感染的患者。

输出格式:

只有一行,输出总共被感染的人数。

输入输出样例
输入样例#1

7 6
1 2
1 3
2 4
2 5
3 6
3 7

输出样例#1

题目分析

这道题是一个搜索题,有人提出可以这样搜:在每次选择切哪一个点的时候,我们考虑切那个总的子节点最多的节点,但其实这是不行的.比如下面这张图.然后我们这搜索,对于一棵树,根节点被感染,枚举要切断的子树,然后更新当前感染节点。

</

这篇关于洛谷 P1041 传染病控制 详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/810550

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl