← 查看本卷题目
组合题5 个小题
已作答 0 / 5

(最长路径)给定一个有向无环图,每条边长度为 11,求图中的最长路径长度。(第五空 2 分,其余 3 分)

输入:第一行是结点数 nn(不超过 100100)和边数 mm,接下来 mm 行,每行两个整数 a,ba,b,表示从结点 aa 到结点 bb 有一条有向边。结点标号从 00 到 (n−1)(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++)            if (graph[queue[head]][i] == 1)            {                (3);                if (degree[i] == 0)                {                    queue[tail] = i;                    tail++;                }            }        (4);    }    ans = 0;    for (i = 0; i < n; i++)    {        a = queue[i];        len[a] = 1;        for (j = 0; j < n; j++)            if (graph[j][a] == 1 && len[j] + 1 > len[a])                len[a] = len[j] + 1;        if ((5))            ans = len[a];    }    cout << ans << endl;    return 0;}
第 34 题填空题

第 3 空应填( )

填写答案