「省选联考 2021」图函数

Sol.

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

• 会产生贡献的 \(v\) 必须满足 \(v \lt u.\)
• \(v\) 与 \(u\) 会产生贡献当且仅当 \(u\) 和 \(v\) 可以仅通过大于 \(v\) 的点互达。

\(\rm Proof: \)

• 当 \(v \gt u\) 时 \(u\) 自己都已经删掉了，肯定不能产生贡献。

• 

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

于是我们可以发现，若定义两点 \((u, v)\) 有贡献当且仅当 \(u \gt 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 \gt 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})\)。

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;
}