P1269 信号放大器

    • 280通过
    • 995提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 树形结构 贪心 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    树型网络是最节省材料的网络。所谓树型网络,是指一个无环的连通网络,网络中任意两个结点间有且仅有一条通信道路。

    网络中有一个结点是服务器,负责将信号直接或间接地发送到各终端机。如图上方,server结点发出一个信号给结点a和c,a再转发给b。如此,整个网络都收到这个信号了。

    但是,实际操作中,信号从一个结点发到另一个结点,会出现信号强度的衰减。衰减量一般由线路长度决定。

    如图下方,边上所标的数字为边的衰减量。假设从server出发一个强度为4个单位的信号,发到结点a后强度衰减为4-3=1个单位。结点a再将其转发给结点b。由于信号强度为1,衰减量为2,因此信号无法发送到b。

    一个解决这一问题的方法是,安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度(从服务器出发时的强度)。

    上图中,若在结点a处安装一个信号放大器,则强度为4的信号发到a处,即被放大至4。这样,信号就可以被发送的网络中的任意一个节点了。为了简化问题,我们假定每个结点只处理一次信号,当它第二次收到某个信号时,就忽略此信号。

    你的任务是根据给出的树型网络,计算出最少需要安装的信号放大器数量。

    输入输出格式

    输入格式:

    第一行一个整数n,表示网络中结点的数量。(n<=20000)

    第2~n+1行,每行描述一个节点的连接关系。其中第i+1行,描述的是结点i的连接关系:首先一个整数k,表示与结点i相连的结点的数量。此后2k个数,每两个描述一个与结点i相连的结点,分别表示结点的编号(编号在1~n之间)和该结点与结点i之间的边的信号衰减量。结点1表示服务器。

    最后一行,一个整数,表示从服务器上出发信号的强度。

    输出格式:

    一个整数,表示要使信号能够传遍整个网络,需要安装的最少的信号放大器数量。

    如果不论如何安装信号放大器,都无法使信号传遍整个网络,则输出“No solution.”

    输入输出样例

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