上三角矩阵压缩还原与 AOE 关键路径

一、 30秒还原法：“倒计数切片”规则

对于 6 个顶点的上三角压缩矩阵（不含主对角线），一维数组的存储数量规律永远是：5、4、3、2、1。

题目给定的数组：

[ 4, 6, ∞, ∞, ∞ | 5, ∞, ∞, ∞ | 4, 3, ∞ | ∞, 3 | 3 ]

直接按规律划线切开，对号入座到矩阵的右上角：

• 第 0 行（切 5 个）：4, 6, ∞, ∞, ∞ $\to$ 边：0指向1(权4)，0指向2(权6)

• 第 1 行（切 4 个）：5, ∞, ∞, ∞ $\to$ 边：1指向2(权5)

• 第 2 行（切 3 个）：4, 3, ∞ $\to$ 边：2指向3(权4)，2指向4(权3)

• 第 3 行（切 2 个）：∞, 3 $\to$ 边：3指向5(权3)

• 第 4 行（切 1 个）：3 $\to$ 边：4指向5(权3)

• 第 5 行（切 0 个）：无指向后继的边

还原后的完整矩阵 $A$：

（主对角线与左下角全填 $\infty$）

$A=\left[\begin{array}{cccccc}\infty & 4& 6& \infty & \infty & \infty \\ \infty & \infty & 5& \infty & \infty & \infty \\ \infty & \infty & \infty & 4& 3& \infty \\ \infty & \infty & \infty & \infty & \infty & 3\\ \infty & \infty & \infty & \infty & \infty & 3\\ \infty & \infty & \infty & \infty & \infty & \infty \end{array}\right]$

二、 绘制有向带权图（严格对照矩阵）

根据切片分析，全图一共只有 7 条边。拓扑图如下：

Plaintext

         (4)          (4)          (3)
     0 ------> 1 ----------> 3 ----------> 5
     |         |             ^             ^
     |         | (5)         |             |
 (6) |         v             | (3)         | (3)
     +-------> 2 ------------+             |
               |                           |
               +---------------------------+ 4

三、 求解关键路径（穷举法）

核心概念：关键路径即为从起点（0）到终点（5）权值总和最大的路径。

列出所有从 0 到 5 的路径并计算权值：

• 路径 ①：0 $\to$ 2 $\to$ 3 $\to$ 5，长度 = 6 + 4 + 3 = 13

• 路径 ②：0 $\to$ 2 $\to$ 4 $\to$ 5，长度 = 6 + 3 + 3 = 12

• 路径 ③：0 $\to$ 1 $\to$ 2 $\to$ 3 $\to$ 5，长度 = 4 + 5 + 4 + 3 = 16 （最大！）

• 路径 ④：0 $\to$ 1 $\to$ 2 $\to$ 4 $\to$ 5，长度 = 4 + 5 + 3 + 3 = 15

最终答案：

• 关键路径：0 $\to$ 1 $\to$ 2 $\to$ 3 $\to$ 5

• 关键路径长度：16

再次为你之前的敏锐点赞！在考场上，就是要保持这种对数据绝对敏感的“找茬”状态！