问题分析

在这道题中，我们需要计算图中每个节点的不稳定性。节点的不稳定性定义为从该节点出发，到达能到达的所有节点时，节点能量的最大值与最小值的差。

每个节点的初始能量随时间的推移而下降，并且通过每条有向边需要消耗时间，导致目标节点能量的变化。节点的能量下降是一个递减过程，且能量值不能低于0。

问题拆解

1. 图的建模：给定的有向图包含n个节点和m条边，节点的初始能量为a[i]。每个节点的能量会随着时间推移而下降，下降的速率为k。我们需要通过深度优先搜索（DFS）或拓扑排序来遍历图，计算每个节点从当前节点出发能够到达的节点的能量最大值和最小值。

2. 不稳定性的计算：对于每个节点，假设它的初始能量为a[i]，当从它出发到达其他节点时，我们根据路径上的边的数量来计算能量的变化。如果到达一个节点时的能量大于0，就记录该节点的能量值。最终不稳定性定义为到达的节点能量的最大值减去最小值。

3. 拓扑排序的使用：由于图是有向无环图（DAG），我们可以利用拓扑排序来保证每个节点的计算顺序：只有当一个节点的所有前驱节点的能量都计算完成时，它的能量才能被计算。这样可以确保我们在计算节点不稳定性时不会出现依赖问题。

解题思路

1. 拓扑排序：我们使用拓扑排序遍历图中的所有节点。通过拓扑排序确保每个节点的所有前驱节点都已经被处理，从而避免循环依赖。

2. DFS遍历：从每个没有入度的节点开始，通过深度优先搜索（DFS）计算每个节点的最大和最小能量。我们在DFS过程中，更新每个节点的最小值和最大值。

3. 能量更新：在DFS中，节点的能量是根据当前节点的初始能量和经过的边数来递减的。每经过一条边，能量减少k，并且能量不能降到负数。

4. 不稳定性计算：对于每个节点，记录其可达节点的最大能量和最小能量，然后计算不稳定性。

复杂度分析

• 时间复杂度：O(n + m)，其中n是节点数，m是边数。因为我们需要遍历所有的节点和边，计算拓扑排序以及DFS遍历图。
• 空间复杂度：O(n + m)，用于存储图的邻接表和节点的状态信息。

代码实现

C++实现

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> a;
vector<int> du;
vector<vector<int>> adj;
vector<bool> vis;
vector<pair<int, int>> dp;

void dfs(int x) {
    vis[x] = true;
    dp[x].first = a[x];  // 最小能量初始化为当前节点能量
    dp[x].second = a[x]; // 最大能量初始化为当前节点能量

    for (int y : adj[x]) {
        if (!vis[y]) {
            dfs(y);
            dp[x].first = min(dp[x].first, max(0, dp[y].first - k));
            dp[x].second = max(dp[x].second, max(0, dp[y].second - k));
        }
    }
}

int main() {
    cin >> n >> m >> k;
    a.resize(n);
    du.resize(n, 0);
    dp.resize(n);
    vis.resize(n, false);
    adj.resize(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        adj[v - 1].push_back(u - 1);
        du[u - 1]++;
    }

    for (int i = 0; i < n; i++) {
        if (du[i] == 0 && !vis[i]) {  // 入度为0的节点
            dfs(i);
        }
    }

    for (int i = 0; i < n; i++) {
        cout << (dp[i].second - dp[i].first) << " ";
    }
    return 0;
}

Python实现

def dfs(x):
    vis[x] = True
    dp[x][0] = a[x]  # 最小能量初始化为当前节点能量
    dp[x][1] = a[x]  # 最大能量初始化为当前节点能量

    for y in adj[x]:
        if not vis[y]:
            dfs(y)
            dp[x][0] = min(dp[x][0], max(0, dp[y][0] - k))
            dp[x][1] = max(dp[x][1], max(0, dp[y][1] - k))

# 输入
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
du = [0] * n
dp = [[0, 0] for _ in range(n)]
vis = [False] * n

# 构建图
for _ in range(m):
    v, u = map(int, input().split())
    adj[v - 1].append(u - 1)
    du[u - 1] += 1

# 深度优先搜索
for i in range(n):
    if du[i] == 0 and not vis[i]:
        dfs(i)

# 输出不稳定性
for i in range(n):
    print(dp[i][1] - dp[i][0], end=" ")

Java实现

import java.util.*;

public class Main {
    static int n, m, k;
    static int[] a;
    static List<Integer>[] adj;
    static int[][] dp;
    static boolean[] vis;
    static int[] du;

    public static void dfs(int x) {
        vis[x] = true;
        dp[x][0] = a[x];  // 最小能量初始化为当前节点能量
        dp[x][1] = a[x];  // 最大能量初始化为当前节点能量

        for (int y : adj[x]) {
            if (!vis[y]) {
                dfs(y);
                dp[x][0] = Math.min(dp[x][0], Math.max(0, dp[y][0] - k));
                dp[x][1] = Math.max(dp[x][1], Math.max(0, dp[y][1] - k));
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        a = new int[n];
        adj = new ArrayList[n];
        dp = new int[n][2];
        vis = new boolean[n];
        du = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int v = sc.nextInt() - 1;
            int u = sc.nextInt() - 1;
            adj[v].add(u);
            du[u]++;
        }

        // 深度优先搜索
        for (int i = 0; i < n; i++) {
            if (du[i] == 0 && !vis[i]) {
                dfs(i);
            }
        }

        // 输出不稳定性
        for (int i = 0; i < n; i++) {
            System.out.print(dp[i][1] - dp[i][0] + " ");
        }
    }
}

题目内容

$Tk$ 有一个由$n$个节点$m$条有向边组成的，节点编号为$1$~$n$的有向无环图，编号i的节点有一股强度为$a_i$的初始能量。 每过一个单位时间，所有节点的能量都会下降$k$(能量不会下降为负值，即如果有节点能量小于k时只会下降至$0$)，$Tk$经过一条边需要花费一个单位时间。

定义每个节点的不确定性，是$Tk$从此节点出发、到能到达的所有节点，到达时的最大能量减去能到达的所有节点，到达时的最小能量(无需保证最大能量节点与最小能量节点在同个简单路径)。你需要求出每个节点的不稳定性。

注意:我们认为，$Tk$到达一个点位时，先将该节点的能量按照经过时间减少$k$(但不低于 $0$)，再记录该节点的能量值。

简单路径是指这样一条路径，其经过的顶点和边互不相同。

输入描述

第一行输入三个正整数 $n,m,k(2≤n≦2×10^5;1≦m≦2×10^5;1≦k≦10^9)$代表这个有向无环图的节点数量、边的数量、每个节点单位时间下降的能量值。

第二行输入$n$个正整数$a_1,a_2,...,a_n(1≦a_i≦10^9)$表示每一个节点的初始能量。

接下来 $m$行，每一行输入两个整数$v_i,u_i(l ≦ v_i,u_i≦n,v_i≠u_i)$表示有一条节点$v_i$到节点 $u_i$的有向边，保证没有重边和自环。

输出描述

输出一行$n$个整数，第$i$个整数表示节点$i$的不稳定性

样例1

输入

5 5 1
8 3 2 5 5
1 2 
1 3
2 3
3 4
4 5

输出

8 2 2 1 0