动态规划与有向无环图的深度解析：拓扑序列驱动的算法设计

核心逻辑与数学原理

有向无环图（Directed Acyclic Graph, DAG）是动态规划（DP）的天然拓扑载体。任何一个带有状态转移方程的 DP 问题，只要其状态之间不存在环形依赖，其状态转移空间在本质上都可以抽象为一张 DAG。

在 DAG 上运行动态规划（通常称为 拓扑序列驱动的 DAG-DP），其核心代数原理在于：拓扑排序的一维线性序列，严格满足动态规划所必须的“无后效性”约束。

1. 拓扑序对状态空间的熟化保障

设状态 $v$ 的计算依赖于前置状态 $u_1, u_2, ext{...}, u_k$。在 DAG 拓扑图上，表现为存在有向边 $(u_i, v)$。

• 无后效性控制：如果我们按照图的拓扑序从小到大依次计算每个节点对应的 DP 状态，那么当算法推进到节点 $v$ 时，所有能够到达 $v$ 的前置节点 $u_i$ 必然已经全部出队并完成了它们的决策。
• 数学本质：拓扑排序将一个网状的分支结构拉平为一条线性的推进链。这确保了在计算当前状态时，前置状态已经是具有“确定性代数解”的熟化状态，后续状态的任何决策也绝不可能反向影响到已计算完毕的节点。

2. 状态转移的两种拓扑触发战术

在具体编码实现时，DAG-DP 存在两种经典的拓扑驱动战术：

• 方案甲：推式（Push-based / 贡献法）
  当一个节点 $u$ 的 DP 状态熟化并准备出队时，它通过所有的出边 $(u, v)$，主动去更新、叠加、或者松弛其后续节点 $v$ 的状态。这非常适合用来做路径计数、方案数累加（如最长食物链问题）。
• 方案乙：拉式（Pull-based / 记忆化搜索）
  直接从最终目标或某些源点出发，顺着有向边的反方向（逆拓扑序）利用 DFS 递归去索要前置状态的值。利用一个 memo 数组拦截重复递归，其递归的底层回溯收敛顺序严格同构于逆拓扑序。

算法推导与状态设计

以经典的有向无环图最长路径与方案数统计为例进行状态设计。

1. 状态定义

• $dp[i]$：从任意合法的拓扑起点出发，到达节点 $i$ 的最长路径长度。
• $cnt[i]$：从任意合法的拓扑起点出发，到达节点 $i$ 且路径长度恰好等于 $dp[i]$ 的最优方案数。

2. 拓扑增量状态转移方程（贡献法）

当零入度节点 $u$ 从拓扑队列中弹出时，其状态 $dp[u]$ 和 $cnt[u]$ 已经绝对熟化。遍历以 $u$ 为起点的每一条出边 $(u, v)$，边权为 $w$：

1. 最长路松弛（发现更优拓扑路径）：
   若 $dp[u] + w > dp[v]$，说明通过 $u$ 中转可以为 $v$ 带来更长的路径。

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

$$cnt[v] = cnt[u] \\ ( ext{方案数完全由 } u ext{ 继承})$$

2. 方案数叠加（发现并列最优拓扑路径）：
   若 $dp[u] + w == dp[v]$，说明找到了另一条到达 $v$ 且长度相同的并列最优路径。

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

C++ 标准源码（拓扑序驱动 DAG-DP 标准模板）

#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] 表示到达节点 i 的最长路
long long cnt[MAXN]; // cnt[i] 表示到达节点 i 且满足最长路条件下的方案数

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

    // 1. 初始化物理边界：将所有入度为 0 的点（拓扑源点）作为 DP 的底座
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
            dp[i] = 0;   // 起点初始最长路径为 0
            cnt[i] = 1;  // 起点初始方案数为 1
        } else {
            dp[i] = -INF; // 其余悬空点初始化为负无穷，防止非法转移
            cnt[i] = 0;
        }
    }

    // 2. 拓扑驱动执行 DP 转移
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 遍历 u 的所有出边更新后续节点 v (推式/贡献法)
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;

            // 过滤未熟化的非法起点转移（如果起点本身不可达则放弃松弛）
            if (dp[u] == -INF) continue; 

            // 分支 A：发现更长的路径，重置 dp 和方案数
            if (dp[u] + w > dp[v]) {
                dp[v] = dp[u] + w;
                cnt[v] = cnt[u];
            }
            // 分支 B：发现并列的最优路径，叠加方案数
            else if (dp[u] + w == dp[v]) {
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
            }

            // 维护拓扑队列
            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. 全局极值汇总
    // 统计所有“出度为 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] = ext{max}(dp[v], dp[u] + 1)$。由于图的拓扑序已经保证了阶段的稳定性，当拓扑队列变空时，直接按顺序输出 $dp[1 ext{...} 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 的拓扑依赖。