「解题报告」[省选联考 2021 A/B 卷] 图函数

我不会最短路了？

显然每对点能对答案造成的贡献是一个前缀，考虑求出每对点能造成贡献的最大时间。

首先能发现，如果 \(v > v'\)，那么假如 \(v \to v' \to u\)，那么 \(v' \to u\) 也一定成立，那么一定已经被删去，反之亦然。所以我们只需要考虑 \(v < v'\) 的点即可。也就是一对点 \((v, u)\) 能够造成贡献当且仅当 \(v, u\) 能够不经过 \([1, v - 1]\) 的点互达。

跑 Floyd，满足中间点 \(k \ge v\) 即可，没了。

是的，\(O(n^3)\)，能过。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005, MAXM = 200005;
int dis[MAXN][MAXN];
int n, m;
long long ans[MAXM];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        dis[u][v] = i;
    }
    for (int i = 1; i <= n; i++) 
        dis[i][i] = m + 1;
    for (int k = n; k >= 1; k--) {
        for (int i = 1; i <= n; i++) if (dis[i][k]) {
            if (i > k) {
                for (int j = 1; j < k; j++) {
                    dis[i][j] = max(dis[i][j], min(dis[i][k], dis[k][j]));
                }
            } else {
                for (int j = 1; j <= n; j++) {
                    dis[i][j] = max(dis[i][j], min(dis[i][k], dis[k][j]));
                }
            }
        }
        for (int i = k; i <= n; i++) {
            ans[min(dis[i][k], dis[k][i])]++;
        }
    }
    for (int i = m; i >= 1; i--) ans[i] += ans[i + 1];
    for (int i = 1; i <= m + 1; i++) {
        printf("%lld ", ans[i]);
    }
    printf("\n");
    return 0;
}