问题分析
在这道题中,我们需要计算图中每个节点的不稳定性。节点的不稳定性定义为从该节点出发,到达能到达的所有节点时,节点能量的最大值与最小值的差。
每个节点的初始能量随时间的推移而下降,并且通过每条有向边需要消耗时间,导致目标节点能量的变化。节点的能量下降是一个递减过程,且能量值不能低于0。
问题拆解
- 图的建模:给定的有向图包含n个节点和m条边,节点的初始能量为a[i]。每个节点的能量会随着时间推移而下降,下降的速率为k。我们需要通过深度优先搜索(DFS)或拓扑排序来遍历图,计算每个节点从当前节点出发能够到达的节点的能量最大值和最小值。
P2830.第2题-简单路径
题目内容
Tk 有一个由n个节点m条有向边组成的,节点编号为1~n的有向无环图,编号i的节点有一股强度为ai的初始能量。
每过一个单位时间,所有节点的能量都会下降k(能量不会下降为负值,即如果有节点能量小于k时只会下降至0),Tk经过一条边需要花费一个单位时间。
定义每个节点的不确定性,是Tk从此节点出发、到能到达的所有节点,到达时的最大能量减去能到达的所有节点,到达时的最小能量(无需保证最大能量节点与最小能量节点在同个简单路径)。你需要求出每个节点的不稳定性。