题目描述

公有云的某个region内，$N$个网络节点组网情况可以使用一个$n\times n$的矩阵matrix表示，在这个组网图中，$matrix[i][j]=p$时，表示用户在编号为$i$的节点访问编号为$j$的节点时，必须在$i$节点上具有 $\ge p$的权限等级($p=0$ 时表示无法通过$i$节点访问$j$节点)，如果用户成功访问了$j$节点，那么它在$j$节点上的权限等级调整为$p$。

exposed为一个整数数组，表示暴露在公网上的网络节点的编号列表。某天扫描发现这批暴露在公网的节点存在被外部恶意攻击风险，且该攻击会影响到可访问的其他节点，并可以持续传递进行攻击。被恶意攻击的节点从公网访问时，攻击者获得了ROOT权限(权限等级为$10$，即最大值)。

题解思路与方法

建模

• 用一个 $N\times N$ 的邻接矩阵 matrix 表示节点间的访问授权门槛：
  • matrix[i][j]=p（p>0） 表示从节点 $i$ 到节点 $j$ 需要在节点 $i$ 上拥有至少 $p$ 级权限；
  • matrix[i][j]=0 表示不可访问。
• exposed 数组为所有直接暴露在公网的节点集合。若不下线某节点 $x$，攻击者可从所有其他暴露节点（初始权限为 10）发起多源 BFS/DFS，对可达节点进行“感染”。

算法

1. 枚举下线节点 $r\in exposed$：