$\large\text{Outline}$
- 众所周知，不加
bitset优化的 $\text{Floyd}$ 通过 $n=10^3$ 的数据也很轻松。
$\large\text{Algorithm}$
计算 $h(G_0)=\sum_{u\in V} f(u,G_0)$：
- 首先，在原图上找到仍存在于当前导出子图的路径，考虑点的存在性显然更优。生成子图反之。
- 遵循该原则，设 $P$ 为 $u\rightarrow v(u>v)$ 某一路径上点的集合，在计算点对 $(u,v)$ 贡献时，$P$ 存在当且仅当 $\forall w\geq\min(u,v) \mid w\in P$。
- 存在满足要求的 $P$ 时，$(u,v)$ 会产生 $1$ 的贡献。由于 $P$ 的约束关涉到中转点和可达性，容易想到使用倒序枚举中转点的 $\text{Floyd}$ 实现。
计算 $\sum_{i=0}^{m}h(G_i)$：
- 考虑单个点对 $(u,v)$，很容易发现，存在时刻 $k\in[0,m+1]$，使得它们在 $[0,k)$ 时刻可达，在 $[k,m]$ 时刻不可达。
- 因此可以在 $\text{Floyd}$ 的过程中计算出 $(u,v)$ 变得相互不可达的时刻。
- 可以令邻接矩阵元素 $g[u][v]$ 表示 $u\rightarrow v$ 路径上最早删去的边被删除的时刻。在 $\text{Floyd}$ 中进行转移，得到最大值，即 $g[u][v] = \max(g[u][v], \min(g[u][k],g[k][v]))$。
$\large\text{Notes}$
- 在 $\text{Floyd}$ 这种小常数的算法中，使用三目运算代替标准库的
min/max函数会有显著的常数优化。