题解

「省选联考 2021」图函数

$\rm Sol.$

首先考虑分析 $f(u, G)$，可以观察出一些性质 ：

  • 会产生贡献的 $v$ 必须满足 $v < u.$

  • $v$ 与 $u$ 会产生贡献当且仅当 $u$ 和 $v$ 可以仅通过大于 $v$ 的点互达。

$\rm Proof: $

  • 当 $v > u$ 时 $u$ 自己都已经删掉了，肯定不能产生贡献。

如上图所示，我们不妨设 $u \to v$ 的路径上必须经过 $x(x < u)$，那么 $x$ 和 $u$ 一定相互可达，$x$ 会在统计 $v$ 的答案之前被删掉。

于是我们可以发现，若定义两点 $(u, v)$ 有贡献当且仅当 $u > v$ 且 $u$ 和 $v$ 之间可以通过大于 $v$ 的点相互到达，则 $h(G)$ 就是在求解 $G$ 中所有点对的贡献之和。

我们考虑 $\rm Floyd$ 算法的过程，实际上就是在不断求解如果只经过当前已经枚举的这些中转点 $k$，有哪些 $u$ 可以走到 $v.$ 于是求解 $h(G)$ 只需要从大到小枚举中转点 $k$，并在 $\rm Floyd$ 的过程中记录下当前 $v = k - 1$ 的答案即可。

进一步观察发现，如果我们按照编号从大到小将边加入图 $G$，那么必然可以找到一个分界点，使得 $u$ 和 $v$ 恰好变为有贡献的点对。容易发现，这个分界点就是 $u$ 和 $v$ 可以相互到达的路径上编号最小的边的最大值。求解这个最大值是简单的，只需要将初始矩阵修改成边的编号，方程改写为 $f_{u, v} = \max\{f_{u, v}, \min\{f_{u, k}, f_{k, v}\}\}$ 即可。

最后用差分维护一下就可以得到最终答案。

时间复杂度 $\Theta(n ^ 3 + m)$，常数很小，写得好的话可以通过。

为了进一步优化复杂度，我们摈弃之前使用 $\rm Floyd$ 的想法。

考虑按编号从大到小枚举所有的边，可以发现每对点 $(u, v)(u > v)$ 都会有一个成为有贡献的点对的分界点。

首先计算 $v$ 可以到达 $u$ 的分界点， $u$ 到 $v$ 的分界点可以通过在反图上进行同样的操作来计算。

有两个显然的性质 ：

  • 有贡献的点对数量最多 $n ^ 2$ 量级。
  • 在加边的过程中有贡献的点对数量不减。

于是考虑计算每条边加入后有贡献的点对的增量。

如上图所示，设当前加入的边为 $x \to y$，$u_1, u_2, u_3, \cdots $ 和 $v_1, v_2, v_3, \cdots$ 分别为能到达 $x$ 的点和 $y$ 能到的点。

考虑用 $\rm bitset$ 记录某个点能直接到达的所有点，能到达的所有点和能到达这个点的所有点，不妨分别设它们为 $E_u, S_u$ 和 $T_u.$

可以发现，若点对 $(u, v)$ 因 $x \to y$ 而增加，需要满足 ：

  • $u$ 在加入 $x \to y$ 之前不能到达 $y.$
  • $u$ 在加入 $x \to y$ 之前要能到达 $x.$
  • 路径上所有点的编号都不小于 $u.$

首先前两个条件可以通过 $T_x \cap (U - T_y)$ 简单地得到，考虑枚举集合中的所有点作为 $u$ 从 $y$ 开始遍历。遍历的过程中，每一步要将 $E_v \cap (U - S_u)$ 中所有编号大于 $u$ 的点作为下一个遍历的点。另外，还要记得随时更新 $S_u.$

考虑这样做的复杂度为什么是对的。因为每一步都会走到一个合法的 $v$，所以答案每一步会增加 $1.$ 并且每走一步都需要计算 $E_v \cap (U - S_u)$，其时间复杂度为 $\Theta(\frac{n}{\omega}).$ 另外，每加入一条边都需要计算 $T_x \cap (U - T_y)$，其时间复杂度也为 $\Theta(\frac{n}{\omega}).$ 于是总时间复杂度为 $\Theta(\frac{n ^ 3 + nm}{\omega})$。

$\rm Code$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10, M = 2e5 + 10;

int n, m, E[N][N], ans[M], Eik, tmp;

int main () {

    scanf("%d%d", &n, &m);
    for (int u, v, i = 1; i <= m; i++)
        scanf("%d%d", &u, &v), E[u][v] = i;

    for (int k = n; k >= 1; k--) {
        for (int i = 1; i <= n; i++) if (E[i][k]) {
            int j; 
            for (j = 1; j + 7 <= n; j += 8) {
                Eik = E[i][k];
                tmp = Eik < E[k][j] ? Eik : E[k][j];
                E[i][j] = E[i][j] > tmp ? E[i][j] : tmp;
                tmp = Eik < E[k][j + 1] ? Eik : E[k][j + 1];
                E[i][j + 1] = E[i][j + 1] > tmp ? E[i][j + 1] : tmp;
                tmp = Eik < E[k][j + 2] ? Eik : E[k][j + 2];
                E[i][j + 2] = E[i][j + 2] > tmp ? E[i][j + 2] : tmp;
                tmp = Eik < E[k][j + 3] ? Eik : E[k][j + 3];
                E[i][j + 3] = E[i][j + 3] > tmp ? E[i][j + 3] : tmp;
                tmp = Eik < E[k][j + 4] ? Eik : E[k][j + 4];
                E[i][j + 4] = E[i][j + 4] > tmp ? E[i][j + 4] : tmp;
                tmp = Eik < E[k][j + 5] ? Eik : E[k][j + 5];
                E[i][j + 5] = E[i][j + 5] > tmp ? E[i][j + 5] : tmp;
                tmp = Eik < E[k][j + 6] ? Eik : E[k][j + 6];
                E[i][j + 6] = E[i][j + 6] > tmp ? E[i][j + 6] : tmp;
                tmp = Eik < E[k][j + 7] ? Eik : E[k][j + 7];
                E[i][j + 7] = E[i][j + 7] > tmp ? E[i][j + 7] : tmp;
            } 
            for ( ; j <= n; ++j) E[i][j] = max(E[i][j], min(E[i][k], E[k][j]));
        }    
        for (int u = k + 1; u <= n; u++)
            ans[min(E[u][k], E[k][u]) - 1]++;
    }

    for (int i = m; i >= 0; i--) ans[i] += ans[i + 1];
    for (int i = 0; i <= m; i++) printf("%d ", ans[i] + n);

    return 0;
}