[省选联考 2021 A/B 卷] 图函数

形式化题目

给定一张包含 $n$ 个顶点和 $m$ 条有向边的简单有向图 $G$ （顶点从 $1$ 到 $n$ 编号，无自环与重边）。

定义函数 $f(u, G)$ 的计算过程如下：

初始图 $G' = G$ ，计数器 $\mathrm{cnt} = 0$ 。
依次枚举顶点 $v = 1, 2, \dots, n$ ：
- 若在当前图 $G'$ 中， $u$ 与 $v$ 互相可达（即同时存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的有向路径），则 $\mathrm{cnt} \leftarrow \mathrm{cnt} + 1$ ，并在 $G'$ 中删除顶点 $v$ 及其所有关联边。
枚举结束后返回 $\mathrm{cnt}$ 。

全图函数值定义为所有顶点函数值的和：

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

记 $G_i$ 为删除按输入顺序给出的前 $i$ 条边后得到的子图（ $0 \le i \le m$ ，其中 $G_0 = G$ ）。要求依次计算并输出 $h(G_0), h(G_1), \dots, h(G_m)$ 共 $m + 1$ 个整数。

暴力解法

思路

最朴素的思路是直接按照题目定义执行模拟：

枚举删边的数量 $k = 0, 1, \dots, m$ ，在激活的边集上构建子图 $G_k$ 。
对当前图 $G_k$ ，枚举起始顶点 $u = 1, 2, \dots, n$ 。
复制当前的可用点集，按顺序遍历 $v = 1, 2, \dots, n$ ：
- 每次通过深度优先搜索（DFS）检查在当前存活顶点中， $u$ 是否能到达 $v$ 以及 $v$ 是否能到达 $u$ 。
- 若双向均可达，将累加器加 $1$ ，并在后续的搜索中将顶点 $v$ 标记为不可用（相当于从图中删去）。
汇总每个 $u$ 的结果得到 $h(G_k)$ 。

该方法完全依据题意进行过程模拟，逻辑直观，可用于验证对题意的理解及产生小规模对拍基准。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-24 00:03
 * update_at: 2026-10-24 00:04
 */
#include <iostream>
#include <vector>

using namespace std;

// brute.cpp：小数据暴力模拟解，用来帮助理解题意并辅助对拍。
// 算法原理：严格按照题意，对每一张图 G_i (i=0..m)，以及每个点 u (1..n)，
// 模拟函数 f(u, G_i) 的计算过程：
// 依次枚举点 v=1..n，若当前子图中 u 能到达 v 且 v 能到达 u，则 cnt++，并将 v 及其关联边删除。
// 最后将所有 f(u, G_i) 累加得到 h(G_i)。
// 复杂度：单次连通性判定 O(n+m)，求一个 f(u) 需做 n 次 DFS 判定，求 h(G) 需 O(n^2(n+m))，
// 共有 m+1 张图，总时间复杂度 O(m * n^2 * (n+m))，仅适用于 n, m <= 15 的极小数据。

const int MAXN = 20;
const int MAXM = 50;

int n, m;
int u_edge[MAXM], v_edge[MAXM];

// 存储当前被激活的边集合与当前存活的点
bool edge_active[MAXM];
bool node_alive[MAXN];
bool vis[MAXN];

// DFS 判定在当前存活点与激活边构成的图中，从 src 是否能到达 dst
bool dfs_reach(int u, int dst) {
    if (u == dst) return true;
    vis[u] = true;
    for (int e = 1; e <= m; ++e) {
        if (!edge_active[e]) continue;
        if (u_edge[e] == u) {
            int v = v_edge[e];
            if (node_alive[v] && !vis[v]) {
                if (dfs_reach(v, dst)) return true;
            }
        }
    }
    return false;
}

bool can_reach(int src, int dst) {
    if (!node_alive[src] || !node_alive[dst]) return false;
    for (int i = 1; i <= n; ++i) vis[i] = false;
    return dfs_reach(src, dst);
}

// 计算当前图下的 f(u)
int calc_f(int u) {
    // 恢复所有点为存活状态
    for (int i = 1; i <= n; ++i) node_alive[i] = true;
    int cnt = 0;
    for (int v = 1; v <= n; ++v) {
        if (can_reach(u, v) && can_reach(v, u)) {
            cnt++;
            node_alive[v] = false; // 删除顶点 v
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        cin >> u_edge[i] >> v_edge[i];
    }

    // G_0 是完整图，删除第 1..k 条边后的图为 G_k
    // 初始所有边都激活
    for (int i = 1; i <= m; ++i) edge_active[i] = true;

    vector<int> ans;
    for (int k = 0; k <= m; ++k) {
        if (k > 0) {
            edge_active[k] = false; // 删去第 k 条边
        }
        int total_h = 0;
        for (int u = 1; u <= n; ++u) {
            total_h += calc_f(u);
        }
        ans.push_back(total_h);
    }

    for (size_t i = 0; i < ans.size(); ++i) {
        cout << ans[i] << (i + 1 == ans.size() ? "" : " ");
    }
    cout << "\n";

    return 0;
}

复杂度

单次 DFS 判定两点连通性需遍历存活点与边，耗时为 $O(n + m)$ 。
计算单个 $f(u, G_k)$ 需进行 $n$ 次双向连通性测试，耗时为 $O(n(n + m))$ 。
求解单张图的 $h(G_k)$ 需枚举 $n$ 个起点，耗时为 $O(n^2(n + m))$ 。
共有 $m + 1$ 张子图需要计算，总时间复杂度为 $O(m \cdot n^2(n + m))$ ，空间复杂度为 $O(n + m)$ 。
该复杂度仅适用于 $n, m \le 15$ 的极小规模数据，面对 $n \le 10^3, m \le 2 \times 10^5$ 的全量数据会严重超时。

瓶颈

暴力模拟的核心性能瓶颈体现在两个相互交织的维度：

外层图状态的重复计算：子图 $G_k$ 是通过依次删边得到的，相邻图之间仅相差一条边，完全重新求解使得前序计算成果无法复用。
内层动态删点的状态依赖：在计算 $f(u, G)$ 时，每个点 $v$ 的存活状态取决于之前的点是否被删除，这种看似动态的先后依赖掩盖了路径连通性的本质拓扑特征。

要取得突破，必须剥离动态删点的表象，将其转化为静态的图论连通性条件。

正解

思路

1. 消除动态删点过程：关键等价刻画

我们深入分析点 $v$ 何时能在 $f(u, G)$ 中对计数器贡献 $1$ ：

当 $v > u$ 时：在计算 $f(u, G)$ 的循环中， $v$ 从 $1$ 递增到 $n$ 。当循环进行到 $v = u$ 时，因为任何点与自身显然互相可达，顶点 $u$ 自身必然在此时被删除！一旦顶点 $u$ 被删去，在后续 $v > u$ 的考察中，图内已不存在点 $u$ ，自然不可能存在任何包含 $u$ 的路径。因此得出重要性质：对于任意 $v > u$ ， $v$ 对 $f(u, G)$ 的贡献恒为 $0$ 。
当 $v = u$ 时：顶点 $u$ 到达自身显然始终成立，贡献恒为 $1$ 。
当 $v < u$ 时：在枚举到 $v$ 时，点 $u$ 尚未被枚举，因而此时点 $u$ 必定存活。所有小于 $v$ 且与 $u$ 双向可达的点虽已被删除，但所有编号大于 $v$ 的点（包括 $u$ ）在此时均完好无损地存活在图中！因此，只要原图中存在一条 $u \rightsquigarrow v$ 的路径和一条 $v \rightsquigarrow u$ 的路径，使得路径上所有除端点外的中间顶点编号均严格大于 $v$ ，这些路径上的所有节点在考察 $v$ 时就绝对不会被删除。反之，若不存在中间点均大于 $v$ 的双向路径，则必定无法在保留的子图中互相可达。

由此，我们交换求和顺序，将 $h(G) = \sum_{u=1}^n f(u, G)$ 转化为考察无序点对：对于满足 $u < v$ 的点对 $(u, v)$ ：

在 $f(u, G)$ 中， $v > u$ ，贡献为 $0$ ；
在 $f(v, G)$ 中，枚举到 $u$ 时， $u < v = \min(u, v)$ 。只要它们在中间顶点均严格大于 $u$ 的子图中互相可达，就产生 $1$ 的贡献。加上每个点自身始终贡献 $1$ ，原问题彻底摆脱了动态删点的过程限制！

2. 动态删边转为双向最大瓶颈路径

子图 $G_k$ 保留的是编号在 $[k + 1, m]$ 内的边。一条有向路径 $P$ 存在于 $G_k$ 中，当且仅当该路径上所有边的最小编号满足：

\min_{e \in P} e \ge k + 1 \iff k \le \min_{e \in P} e - 1

为了使点对 $(u, v)$ 能在尽可能多的 $G_k$ 中产生贡献，我们定义 $f[u][v]$ 为：从 $u$ 到 $v$ 且所有中间顶点均严格大于 $\min(u, v)$ 的路径中，路径上最小边编号（瓶颈）的最大值：

f[u][v] = \max_{P: u \rightsquigarrow v, \text{中间点} > \min(u, v)} \left( \min_{e \in P} e \right)

对于任意 $u < v$ ，两点在中间点均大于 $u$ 的条件下双向连通的最大瓶颈即为：

W(u, v) = \min(f[u][v], f[v][u])

当 $W(u, v) > 0$ 时，该点对在删边数量 $k \in [0, W(u, v) - 1]$ 的所有子图 $G_k$ 中都产生 $1$ 的贡献。利用差分数组，在 $W(u, v)$ 处打上标记，最后做一次后缀和即可 $O(m)$ 还原出全部 $h(G_k)$ 。

3. 倒序 Floyd 动态规划

求解条件约束为“中间点全部大于 $\min(i, j)$ ”的瓶颈路径，正好契合 Floyd 算法按节点枚举的特征。

我们将中转点 $k$ 倒序枚举（ $k = n, n-1, \dots, 1$ ）。当使用 $k$ 作为中间点松弛点对 $(i, j)$ 时， $k$ 合法的充要条件是：

k > \min(i, j)

此时的状态转移方程为：

f[i][j] \leftarrow \max\big(f[i][j], \min(f[i][k], f[k][j])\big)

为提升效率，利用等价条件 $k > \min(i, j) \iff (i < k) \lor (j < k)$ ，将循环拆分为两段：

当 $i < k$ 时：必然有 $\min(i, j) \le i < k$ ，对所有 $1 \le j \le n$ 均可进行转移；
当 $i > k$ 时：需满足 $j < k$ 才能保证 $\min(i, j) = j < k$ 。

通过行指针提取与紧凑连续访存，内层循环运算次数仅约 $\frac{2}{3}n^3$ ，极其高效。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-24 00:03
 * update_at: 2026-10-24 00:04
 */
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1005;
const int MAXM = 200005;

// 全局变量与数组
int n, m;

// f[u][v] 表示在原图中，从 u 到 v 且所有中间点编号均严格大于 min(u, v) 的路径中，
// 路径上最小边编号（瓶颈）的最大值。
// 若不存在这样的路径，则 f[u][v] = 0。
int f[MAXN][MAXN];

// ans_cnt[w] 记录使某对点产生贡献的瓶颈边权 w 的频数
// 用于差分与后缀和，最终 ans_cnt[k + 1] 即为 h(G_k) 的答案
int ans_cnt[MAXM];

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    // 读入 m 条有向边，边的输入顺序即为边的编号 1..m
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        f[u][v] = i; // 若有重边，后输入的边编号更大，直接覆盖即可
    }

    // 倒序 Floyd 动态规划：外层枚举中转点 k 从 n 到 1
    // 状态转移限制：中转点 k 必须满足 k > min(i, j)
    for (int k = n; k >= 1; --k) {
        int *fk = f[k];

        // 第一类情况：i < k，此时必然有 min(i, j) <= i < k，故对所有 j (1 <= j <= n) 均可转移
        for (int i = 1; i < k; ++i) {
            int fik = f[i][k];
            if (!fik) continue;
            int *fi = f[i];
            for (int j = 1; j <= n; ++j) {
                int fkj = fk[j];
                if (!fkj) continue;
                int val = min(fik, fkj);
                if (val > fi[j]) {
                    fi[j] = val;
                }
            }
        }

        // 第二类情况：i > k，此时必须满足 j < k 才能保证 min(i, j) = j < k
        for (int i = k + 1; i <= n; ++i) {
            int fik = f[i][k];
            if (!fik) continue;
            int *fi = f[i];
            for (int j = 1; j < k; ++j) {
                int fkj = fk[j];
                if (!fkj) continue;
                int val = min(fik, fkj);
                if (val > fi[j]) {
                    fi[j] = val;
                }
            }
        }
    }

    // 统计每对点 (u, v) (1 <= u <= v <= n) 产生贡献的有效边权区间
    for (int u = 1; u <= n; ++u) {
        // 当 u == v 时，自身到自身在任何子图中均连通，在所有 m+1 张图中均存在
        ans_cnt[m + 1]++;

        // 当 u < v 时，中间点必须全部 > u，瓶颈为 min(f[u][v], f[v][u])
        for (int v = u + 1; v <= n; ++v) {
            int w = min(f[u][v], f[v][u]);
            if (w > 0) {
                // 边权最小值 >= w 的子图 G_0..G_{w-1} 中该点对均存在
                // 对应下标 0..w-1，差分打标在 w 处
                ans_cnt[w]++;
            }
        }
    }

    // 计算后缀和，还原出每张子图的答案
    for (int i = m; i >= 1; --i) {
        ans_cnt[i] += ans_cnt[i + 1];
    }

    // 输出 G_0, G_1, ..., G_m 的答案 h(G_k) = ans_cnt[k + 1]
    for (int k = 0; k <= m; ++k) {
        cout << ans_cnt[k + 1] << (k == m ? "" : " ");
    }
    cout << "\n";

    return 0;
}

复杂度

时间复杂度：
- 倒序 Floyd 阶段：外层枚举 $k$ ，内层循环总次数约为 $\sum_{k=1}^n (k-1)(2n-k) \approx \frac{2}{3} n^3$ 。在 $n = 1000$ 下仅约 $6.67 \times 10^8$ 次简单整数比对操作，耗时约 $800$ ms。
- 点对统计与后缀和：遍历点对耗时 $O(n^2)$ ，后缀和计算与输出耗时 $O(m)$ 。
- 总时间复杂度为 $O(n^3 + m)$ ，完全满足 2.0s 的时限要求。
空间复杂度：
- 矩阵 $f$ 占用内存约 $1005 \times 1005 \times 4 \text{ B} \approx 4.0 \text{ MB}$ 。
- 差分数组占用内存约 $200005 \times 4 \text{ B} \approx 0.8 \text{ MB}$ 。
- 总空间复杂度为 $O(n^2 + m)$ ，远低于 $512$ MB 的空间上限。

总结

本题的精髓在于通过严密的代数与拓扑分析，拆解看似不可逆的“动态删点”与“动态删边”过程：

顺流而下的删点观察：发现点 $u$ 在考察自身时才会被删除，从而推导出 $v > u$ 恒无贡献，将无序点对的生效条件精准锚定在“中间点均大于 $\min(u, v)$ 的诱导子图”上。
瓶颈路径与差分转化：将动态删边转化为求路径上的最大瓶颈边权，巧妙应用差分与后缀和化解多子图的重复统计。
定向约束的 Floyd 优化：将中间点的编号约束映射为 Floyd 的中转点倒序遍历，并通过条件拆解将常数优化至 $\frac{2}{3}$ ，实现了理论证明与工业级运行效率的统一。

测试点编号	$n \le$	$m\le$
$1 \sim 4$	$10$	$10$
$5 \sim 11$	$100$	$2 \times {10}^3$
$12 \sim 20$	${10}^3$	$5 \times {10}^3$
$21 \sim 25$	${10}^3$	$2 \times {10}^5$