网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
信号放大器
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | booster.in | 输出文件 | booster.out |
【问题描述】
树型网络是最节省材料的网络。所谓树型网络,是指一个无环的连通网络,网络中任意两个结点间有且仅有一条通信道路。
网络中有一个结点是服务器,负责将信号直接或间接地发送到各终端机。如图6-4,server结点发出一个信号给结点a和c,a再转发给b。如此,整个网络都收到这个信号了。
server a b ●-------------○----------○ │ │ ○
但是,实际操作中,信号从一个结点发到另一个结点,会出现信号强度的衰减。衰减量一般由线路长度决定。
server 3 a 2 b ●-------------○----------○ │ │1 ○
如上图,边上所标的数字为边的衰减量。假设从server出发一个强度为4个单位的信号,发到结点a后强度衰减为4-3=1个单位。结点a再将其转发给结点b。由于信号强度为1,衰减量为2,因此信号无法发送到b。
一个解决这一问题的方法是,安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度(从服务器出发时的强度)。
上图中,若在结点a处安装一个信号放大器,则强度为4的信号发到a处,即被放大至4。这样,信号就可以被发送的网络中的任意一个节点了。为了简化问题,我们假定每个结点只处理一次信号,当它第二次收到某个信号时,就忽略此信号。
你的任务是根据给出的树型网络,计算出最少需要安装的信号放大器数量。
【输入】
第一行一个整数n,表示网络中结点的数量。(n<=100000)
第2~n+1行,每行描述一个节点的连接关系。其中第i+1行,描述的是结点i的连接关系:首先一个整数k,表示与结点i相连的结点的数量。此后2k个数,每两个描述一个与结点i相连的结点,分别表示结点的编号(编号在1~n之间)和该结点与结点i之间的边的信号衰减量。结点1表示服务器。
最后一行,一个整数,表示从服务器上出发信号的强度。
【输出】
一个整数,表示要使信号能够传遍整个网络,需要安装的最少的信号放大器数量。
如果不论如何安装信号放大器,都无法使信号传遍整个网络,则输出“No solution.”
【样例】
booster.in booster.out
4 1
2 2 3 3 1
2 1 3 4 2
1 1 1
1 2 2
4