Deep Dive into Dynamic Programming and Directed Acyclic Graphs: Algorithm Design Driven by Topological Sequences

Core Logic and Mathematical Principles

Directed Acyclic Graphs (DAGs) serve as a natural topological framework for Dynamic Programming (DP). Any DP problem that involves state transition equations can essentially be abstracted as a DAG, provided that there are no cyclic dependencies between states.

Running dynamic programming on a DAG (commonly referred to as Topological Sequence Driven DAG-DP) hinges on a core algebraic principle: the one-dimensional linear sequence of topological sorting strictly adheres to the "no aftereffect" constraint required by dynamic programming.

1. Topological Order Ensures Familiarization of State Space

Let the computation of state $v$ depend on predecessor states $u_1, u_2, \text{...}, u_k$. In the DAG topological graph, this is represented by the existence of directed edges $(u_i, v)$.

• No Aftereffect Control: If we compute each node's corresponding DP state in ascending order according to the graph's topological order, then when the algorithm reaches node $v$, all predecessor nodes $u_i$ that can reach $v$ must have been fully dequeued and completed their decisions.
• Mathematical Essence: Topological sorting flattens a branched structure into a linear progression chain. This ensures that when calculating the current state, the predecessor states are already in a familiarized state with a "deterministic algebraic solution", and any subsequent decisions cannot retroactively affect nodes that have already been computed.

2. Two Topological Trigger Tactics for State Transition

In practical coding implementations, there are two classic topological-driven tactics for DAG-DP:

• Strategy A: Push-based (Contribution Method)
  When a node $u$'s DP state is familiarized and ready to be dequeued, it proactively updates, accumulates, or relaxes the states of its successor nodes $v$ through all outgoing edges $(u, v)$. This method is particularly suitable for path counting and scheme accumulation (e.g., the longest food chain problem).
• Strategy B: Pull-based (Memoization Search)
  Starting from the final target or certain source points, it recursively requests the values of predecessor states in the reverse direction along the directed edges (inverse topological order) using DFS. A memo array is employed to intercept repeated recursion, and the underlying backtracking of this recursion strictly mirrors the inverse topological order.

Algorithm Derivation and State Design

Taking the classic problem of longest path and scheme count statistics in a directed acyclic graph as an example for state design.

1. State Definition

• $dp[i]$: The longest path length from any valid topological starting point to node $i$.
• $cnt[i]$: The optimal scheme count for reaching node $i$ with a path length exactly equal to $dp[i]$ from any valid topological starting point.

2. Topological Incremental State Transition Equation (Contribution Method)

When a zero in-degree node $u$ is dequeued from the topological queue, its states $dp[u]$ and $cnt[u]$ are fully familiarized. Traverse each outgoing edge $(u, v)$ starting from $u$, with edge weight $w$:

1. Longest Path Relaxation (Discovering a Better Topological Path):
   If $dp[u] + w > dp[v]$, it indicates that passing through $u$ can provide a longer path to $v$.

$$dp[v] = dp[u] + w$$

$$cnt[v] = cnt[u] \\ (\text{the scheme count is entirely inherited from } u)$$

2. Scheme Count Accumulation (Discovering Parallel Optimal Topological Paths):
   If $dp[u] + w == dp[v]$, it indicates that another optimal path to $v$ of the same length has been found.

$$cnt[v] = (cnt[v] + cnt[u]) \\ \text{mod } MOD$$

C++ Standard Source Code (Topological Sequence Driven DAG-DP Standard Template)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 100005;
const long long MOD = 1000000007LL;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct Edge {
    int to;
    long long weight;
};

std::vector<Edge> adj[MAXN];
int in_degree[MAXN];
int out_degree[MAXN];

long long dp[MAXN];  // dp[i] represents the longest path to node i
long long cnt[MAXN]; // cnt[i] represents the number of schemes to reach node i under the longest path condition

void dag_dp(int n) {
    std::queue<int> q;

    // 1. Initialize physical boundaries: Treat all nodes with an in-degree of 0 (topological sources) as the base for DP
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
            dp[i] = 0;   // Initial longest path for the starting point is 0
            cnt[i] = 1;  // Initial scheme count for the starting point is 1
        } else {
            dp[i] = -INF; // Other dangling points are initialized to negative infinity to prevent illegal transitions
            cnt[i] = 0;
        }
    }

    // 2. Topology-driven execution of DP transitions
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Traverse all outgoing edges from u to update subsequent node v (Push-based/Contribution method)
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;

            // Filter out invalid nodes with un-familiarized state (if the starting point is unreachable, skip relaxation)
            if (dp[u] == -INF) continue; 

            // Branch A: Discover a longer path, reset dp and scheme count
            if (dp[u] + w > dp[v]) {
                dp[v] = dp[u] + w;
                cnt[v] = cnt[u];
            }
            // Branch B: Discover a parallel optimal path, accumulate scheme count
            else if (dp[u] + w == dp[v]) {
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
            }

            // Maintain the topological queue
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{v, w});
        in_degree[v]++;
        out_degree[u]++;
    }

    dag_dp(n);

    // 3. Global extreme value summary
    // Count the optimal states of all "sink nodes with out-degree 0"
    long long max_path_len = -INF;
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] == 0) {
            max_path_len = std::max(max_path_len, dp[i]);
        }
    }

    long long total_schemes = 0;
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] == 0 && dp[i] == max_path_len) {
            total_schemes = (total_schemes + cnt[i]) % MOD;
        }
    }

    if (max_path_len < 0) {
        std::cout << "No valid path\n";
    } else {
        std::cout << max_path_len << " " << total_schemes << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 未区分“图的拓扑源点”与“题目指定的逻辑起点”：
   如果在运行期，题目显式指定了路径必须从某个固定点 $S$ 开始，很多选手会习惯性地在初始化时把所有 in_degree == 0 的点都赋值为 dp = 0, cnt = 1。这样会导致其他本不该被纳入统计的零入度源点混入转移，计算出来的方案数和路径长会比真实值偏大。

• 战术纠错：如果题目限定了起点 $S$，那么只有 $dp[S] = 0, cnt[S] = 1$，其余包括入度为 0 的所有节点都必须强行置为 dp = -INF, cnt = 0。

2. 状态转移时没有拦截 -INF 的无效废弃节点：
   如上所述，若非题目指定起点的其他零入度点保持为 -INF，当它们出队时，如果代码没有进行 if (dp[u] == -INF) continue; 的条件拦截，直接去执行 dp[u] + w 可能会因为负溢出，从而错误地松弛、污染了其他节点的合法状态。

经典 NOIP/洛谷 真题

1. 洛谷 P1137 旅行计划

• 题意描述：
  小明要去 $N$ 个城市旅行，城市之间共有 $M$ 条单向道路。由于路途遥远，路线只能从编号小的城市通往编号大的城市（天然保证了是有向无环图）。小明想知道，对于每个城市，以它为终点的旅行路线最多能包含多少个城市。
• 问题本质与核心思路：
  标准有向无环图单源/多源最长路径 DP。
  定义 $dp[i]$ 为到达城市 $i$ 的最长路径（包含的城市数量）。由于路径本身无负权且所有零入度点都是合法起点，初始化所有 in_degree[i] == 0 的点 $dp[i] = 1$。跑标准的 Kahn 拓扑排序，当节点 $u$ 弹出时，遍历出边 $(u, v)$，执行状态转移方程：$dp[v] = \text{max}(dp[v], dp[u] + 1)$。由于图的拓扑序已经保证了阶段的稳定性，当拓扑队列变空时，直接按顺序输出 $dp[1 \text{...} n]$ 即为各点的最优解。

2. 洛谷 P1954 [NOI2010] 航空管制

• 题意描述：
  有 $N$ 架飞机需要起飞，起飞必须满足 $M$ 个前置依赖关系（形如飞机 $A$ 必须在飞机 $B$ 之前起飞）。同时，每架飞机都有一个最晚起飞位置限制 $k_i$，表示这架飞机必须在前 $k_i$ 个起飞。要求：1. 求出一个全局合法的起飞序列。2. 在满足所有限制的前提下，求出每架飞机各自能够争取到的最早起飞位置。
• 问题本质与核心思路：
  这是一道将反向拓扑排序与贪心决策（DAG 变阵）结合的综合应用题。
  直观地从前往后安排位置极难处理，因为当前做出的决策会严重制约后续的限制。
  逆向拓扑战术重构：将时间线倒过来考虑，求最早起飞位置等价于在反向图上求该飞机的最晚起飞位置。

1. 第一步：建立反向图，原来的 $A \to B$ 变更为 $B \to A$。将飞机的最晚起飞限制转化为反向图中的限制。
2. 第二步：利用最大堆（优先队列）维护当前反向入度为 0 的飞机。每次起飞，我们都贪心地选择最晚起飞限制 $k_i$ 最大的那架飞机放在反向序列的最后面。这样可以把更多的“宽容度”留给后面那些限制严格的飞机。
3. 第三步（求单架飞机 $X$ 的最早位置）：为了让 $X$ 尽可能靠前，在反向拓扑中就要让它尽可能靠后。我们可以直接在反向拓扑的迭代中，故意不让 $X$ 进入起飞队列，直到队列变空、且不安排 $X$ 算法再也无法推进时，此时腾出来的反向空位，本质上就是 $X$ 在反向图上能被卡住的最早时点。经过整型平移后，即为原图上的最早起飞位置。整个解法完美压制了 DAG 的拓扑依赖。