NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 28 题

（最长路径）给定一个有向无环图，每条边长度为 $1$，求图中的最长路径长度。（第五空 2 分，其余 3 分）

输入：第一行是结点数 $n$（不超过 $100$）和边数 $m$，接下来 $m$ 行，每行两个整数 $a,b$，表示从结点 $a$ 到结点 $b$ 有一条有向边。结点标号从 $0$ 到 $(n-1)$。 输出：最长路径长度。

提示：先进行拓扑排序，然后按照拓扑序计算最长路径。

#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100];     // 记录每个结点的入度
int len[100];        // 记录以各结点为终点的最长路径长度
int queue[100];      // 存放拓扑排序结果
int main()
{
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            graph[i][j] = 0;
    for (i = 0; i < n; i++)
        degree[i] = 0;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b;
        graph[a][b] = 1;
        (1);
    }
    tail = 0;
    for (i = 0; i < n; i++)
        if ((2))
        {
            queue[tail] = i;
            tail++;
        }
    head = 0;
    while (tail < n - 1)
    {
        for (i = 0; i < n; i++

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题就是DAG最长路的经典考法：先统计入度，把入度为0的节点入队（拓扑排序），然后按队列顺序依次处理，每处理一个点就把它指向的后继入度减1，若后继入度变0则入队。最后按拓扑序做一次DP，len[x]表示以x为终点的最长路径，答案就是所有len的最大值。

最容易栽跟头的地方是拓扑排序里入度更新的细节：填边时degree[b]++，处理点时degree[i]--，如果写反了或者漏掉++/--，后面入度永远不为0，队列跑不完。还有DP方向，len[x]是以x为终点的最长路，更新后继时要len[后继]=max(len[后继], len[x]+1)，别写成从x出发的最长路。最后取答案时，因为拓扑序不一定按len大小排，必须遍历所有len取max，只填最后一个len[a]当答案会漏掉更长的分支。

考点与命题意图

这题考的是DAG上的最长路径，本质是拓扑排序 + 动态规划。命题人喜欢把算法拆成几个填空，让你补全入度统计、队列操作、DP转移和取最大值。考点集中在：邻接矩阵存图、入度数组维护、拓扑排序Kahn算法的指针移动、以及DP状态定义与转移方向。

概念速览

• 拓扑排序：对有向无环图做线性排列，使得每条边(u,v)都有u排在v前面。Kahn算法就是不断把入度为0的点入队，然后删掉它的出边，若某点入度变0就入队。
• DP on DAG：在拓扑序上DP天然无后效性。这里len[x]定义为“以x为终点的最长路径长度”，初始len[入度为0的点]=1（因为路径至少包含这个点本身，边长为1，所以长度就是点数）。转移就是：若x→y有边，则len[y] = max(len[y], len[x] + 1)。