题目理解

我们有一个 $n$ 个点 $m$ 条边的有向图 $G$，定义函数 $f(u,G)$：

1. 初始化 $cnt = 0$，$G' = G$
2. 从 $1$ 到 $n$ 依次枚举顶点 $v$：
   • 如果当前图 $G'$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在
   • 则 $cnt + 1$，并在 $G'$ 中删去顶点 $v$ 及与其相关的边
3. 返回 $cnt$

需要计算：

$$h(G) = \sum_{i=1}^n f(i, G)$$

更进一步，记删除前 $i$ 条边后的图为 $G_i$，需要求出所有 $h(G_i)$ 的值。

---

关键观察

1. 函数 $f(u,G)$ 的本质

对于给定的 $u$，函数 $f(u,G)$ 实际上计算的是：从 $u$ 出发，按照编号从小到大顺序，能够双向连通（即存在 $u \to v$ 和 $v \to u$ 的路径）且路径上所有中间点的编号都不小于当前考虑点的那些顶点 $v$ 的数量。

2. 转化为点对贡献

考虑点对 $(i,j)$（其中 $i \leq j$），它会对 $h(G)$ 产生贡献当且仅当：

• 存在 $i \to j$ 和 $j \to i$ 的路径
• 路径上的所有中间点的编号都不小于 $i$

---

算法设计

1. 定义关键量

设 $T(i,j)$ 表示满足以下条件的最小边权的最大值：

• 存在 $i \to j$ 和 $j \to i$ 的路径
• 路径上的边编号都不超过 $T(i,j)$

特别地，当 $i = j$ 时，$T(i,j) = m + 1$

2. 贡献分析

点对 $(i,j)$ 会对所有 $h(G_t)$（其中 $0 \leq t < T(i,j)$）产生 $1$ 的贡献。

3. 动态规划求解

使用类 Floyd 算法，但按顶点编号从大到小枚举中间点：

for(int k = n; k >= 1; k--) {
    for(int i = 1; i <= n; i++) {
        int t = d[i][k];
        for(int j = 1; j <= n; j++) {
            d[i][j] = max(d[i][j], min(t, d[k][j]));
        }
    }
    
    // 计算当前k产生的贡献
    for(int j = k; j <= n; j++) {
        int T = min(d[j][k], d[k][j]);
        if(T) h[T-1]++;
    }
}

4. 后缀和计算

由于贡献是累积的，需要计算后缀和：

for(int i = m; i >= 0; i--) {
    h[i] += h[i+1];
}

---

算法正确性证明

1. 动态规划的正确性

按 $k$ 从大到小枚举保证了路径上的中间点编号都不小于当前考虑的起点编号，这正好符合 $f(u,G)$ 的定义要求。

2. 贡献计算的正确性

对于点对 $(i,j)$，$T(i,j)$ 表示最大的边权阈值，在这个阈值内双向连通性仍然保持。因此对于所有删除边数 $t < T(i,j)$ 的图，该点对都会产生贡献。

---

复杂度分析

时间复杂度：

• Floyd 算法：$O(n^3)$
• 贡献统计：$O(n^2)$
• 后缀和计算：$O(m)$

空间复杂度：

• 邻接矩阵：$O(n^2)$
• 答案数组：$O(m)$

对于 $n \leq 10^3$，$m \leq 2 \times 10^5$ 的数据范围，该算法在合理时间内可以完成计算。

---

代码实现要点

1. 初始化：

   • 邻接矩阵 d[i][j] 存储边编号，无边则为 0
   • 自环 d[i][i] = m + 1

2. 动态规划更新：

   • 使用 max 和 min 组合来维护路径的最小边权最大值
   • 从大到小枚举中间点 $k$

3. 贡献统计：

   • 只在 $j \geq k$ 时统计贡献，避免重复
   • 使用 min(d[j][k], d[k][j]) 确保双向连通

4. 答案输出：

   • 后缀和计算得到最终答案
   • 输出 $m+1$ 个结果

---

算法标签

• 图论
• 动态规划
• Floyd算法

---

总结

本题的关键在于将复杂的函数计算转化为点对贡献问题，通过巧妙的动态规划和图论性质分析，避免了直接模拟函数计算的高复杂度。算法充分利用了问题的特殊结构，实现了高效求解。