题库 NOIP CSP J/S信奥赛 题目列表 (最长路径)给定一个有向无环图,每条边长度为1,求...
问答题

(最长路径)给定一个有向无环图,每条边长度为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++)

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;

}

题目信息
提高组 初赛 2017 完善程序
-
正确率
0
评论
149
点击
QQ
公众号
客服
扫一扫