P1084 疫情控制

    • 1.2K通过
    • 4.9K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 二分答案 倍增 排序 树形结构 贪心 NOIp提高组 2012 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    $H$ 国有 $n $ 个城市,这 $n$ 个城市用 $ n-1 $ 条双向道路相互连通构成一棵树, $1 $ 号城市是首都,也是树中的根节点。

    $H $ 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

    现在,在 $H$ 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

    请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

    输入输出格式

    输入格式:

    第一行一个整数 $ n$ ,表示城市个数。

    接下来的 $n-1$ 行,每行 $ 3 $ 个整数, $u,v,w$ ,每两个整数之间用一个空格隔开,表示从城市 $u $ 到城市 $ v$ 有一条长为 $w$ 的道路。数据保证输入的是一棵树,且根节点编号为 $1$ 。

    接下来一行一个整数 $m$ ,表示军队个数。

    接下来一行 $m $ 个整数,每两个整数之间用一个空格隔开,分别表示这 $m$ 个军队所驻扎的城市的编号。

    输出格式:

    一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出 $-1$ 。

    输入输出样例

    输入样例#1: 复制
    4 
    1 2 1 
    1 3 2 
    3 4 3 
    2 
    2 2
    输出样例#1: 复制
    3

    说明

    【输入输出样例说明】

    第一支军队在 $2$ 号点设立检查点,第二支军队从 $2$ 号点移动到 $ 3$ 号点设立检查点,所需时间为 $3$ 个小时。

    【数据范围】

    保证军队不会驻扎在首都。

    对于 20%的数据, $2≤ n≤ 10$ ;

    对于 40%的数据, $2 ≤n≤50,0<w <10^5$ ;

    对于 60%的数据, $2 ≤ n≤1000,0<w <10^6$ ;

    对于 80%的数据, $2 ≤ n≤10,000$ ;

    对于 100%的数据, $2≤m≤n≤50,000,0<w <10^9$ 。

    NOIP 2012 提高组 第二天 第三题

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。