D. Fight Against Traffic - 题解

比赛与标签

比赛: Educational Codeforces Round 40 (Rated for Div. 2) 标签: dfs and similar, graphs, shortest paths 难度: *1600

题目大意喵~

主人，你好呀~！这道题是关于一个叫 Nsk 的小镇的故事，喵~

小镇里有 n 个路口和 m 条双向道路。市长先生每天要从 s 路口开车去 t 路口上班。现在，市议会决定要新建一条路来改善交通。但是呢，市长先生特别喜欢他现在的开车路线，不希望他从家到公司的最短通勤时间（也就是经过的最少道路数）变得更短。

我们的任务就是，找出所有当前没有路连接的路口对 (u, v)，如果在它们之间新建一条路，从 s 到 t 的最短距离不会减少。我们要计算出这样合法的路口对一共有多少个，呐。

简单来说，就是：

输入: 图的节点数 n，边数 m，起点 s，终点 t，以及 m 条已有的边。
输出: 可以新建道路，且不会使 s 到 t 最短路变短的方案数。

解题思路大揭秘！

这道题的核心是“最短路”，而且图里的所有道路都没有权重（可以看作权重都为1）。一看到无权图的最短路，我们聪明的猫娘脑海里第一个蹦出来的就是 BFS（广度优先搜索） 啦！它简直是为这类问题量身定做的，喵~

我们的目标是，新修一条路 (u, v) 后，s 到 t 的最短路长度 new_dist 必须大于等于原来的最短路长度 old_dist。

那么，解题思路就很清晰啦，可以分成几步走：

第一步：计算原始最短路

首先，我们得知道市长先生原来的通勤时间是多少。也就是，在当前图上，s 到 t 的最短距离 old_dist 是多少。用一次从 s 开始的 BFS 就能轻松搞定啦！

第二步：思考新路的“威胁”

当我们新建一条路 (u, v) 时，它可能会创造出一条比原来更短的 s-t 路径。这条新路可能会怎么被利用呢？有两种可能的方式：

从 s 出发，先走到 u，然后通过新路 (u, v) 到达 v，最后从 v 走到 t。这条新路径的长度是：(s到u的最短距离) + 1 + (v到t的最短距离)。
从 s 出发，先走到 v，然后通过新路 (v, u) 到达 u，最后从 u走到 t。这条新路径的长度是：(s到v的最短距离) + 1 + (u到t的最短距离)。

为了让市长先生满意，这两条新路径的长度都必须 >= old_dist。

第三步：预处理所有点的距离

从第二步可以看出，对于任意一对备选的路口 (u, v)，我们都需要知道 s 到 u、s 到 v、u 到 t、v 到 t 的最短距离。一个一个算太慢了啦！

聪明的做法是，我们提前把所有需要的信息都算好！

运行一次从 s 开始的 BFS，得到 s 到所有其他路口 i 的最短距离，记作 dist_s[i]。
运行一次从 t 开始的 BFS，得到 t 到所有其他路口 i 的最短距离，记作 dist_t[i]。

这样，对于任何一个点 i，我们都能立刻知道 dist(s, i) 和 dist(t, i) 了！是不是很方便呢？

第四步：枚举所有可能的方案并计数

现在万事俱备，只欠枚举啦！我们遍历所有可能的路口对 (i, j) (为了不重复，可以假设 i < j)。

对于每一对 (i, j)：

首先要检查它们之间是不是已经有路了。如果已经有路，就不能再修了，直接跳过，喵~。
如果没路，我们就来判断修路后会不会“闯祸”。根据我们第二步的分析，需要同时满足以下两个条件：
- dist_s[i] + 1 + dist_t[j] >= old_dist
- dist_s[j] + 1 + dist_t[i] >= old_dist
如果这两个条件都成立，说明在 (i, j) 之间修路是安全的，不会缩短市长的通勤时间。我们就把计数器加一！

把所有可能的路口对都检查一遍后，最终得到的计数就是答案啦！

总结一下就是：两次BFS + 一次双重循环枚举，搞定！

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <queue>

// 一个标准的BFS函数，用来计算从某个起点到图中所有点的最短距离喵~
// start_node: 起点
// n: 总节点数
// adj: 图的邻接表表示
// dist: 用来存储计算出的最短距离的数组
void bfs(int start_node, int n, const std::vector<std::vector<int>>& adj, std::vector<int>& dist) {
    // 初始化所有距离为-1，表示还没访问过
    dist.assign(n + 1, -1); 
    std::queue<int> q;

    // 起点到自己的距离当然是0啦
    dist[start_node] = 0;
    q.push(start_node);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 遍历当前节点的所有邻居
        for (int v : adj[u]) {
            if (dist[v] == -1) { // 如果邻居v还没被访问过
                dist[v] = dist[u] + 1; // 更新v的距离
                q.push(v);             // 把v加入队列，待会从它继续探索
            }
        }
    }
}

int main() {
    // 加速一下输入输出，跑得更快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, s, t;
    std::cin >> n >> m >> s >> t;

    // 用邻接表来存图的结构
    std::vector<std::vector<int>> adj(n + 1);
    // 用一个二维布尔数组来快速检查两个点之间是否已经有路了，O(1)查询很香的！
    std::vector<std::vector<bool>> exists(n + 1, std::vector<bool>(n + 1, false));

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        exists[u][v] = true;
        exists[v][u] = true;
    }

    // 这两个数组分别存s到各点、t到各点的最短距离
    std::vector<int> ds, dt;
    
    // 第一次BFS：从s出发，计算s到所有点的距离
    bfs(s, n, adj, ds);
    // 第二次BFS：从t出发，计算t到所有点的距离
    bfs(t, n, adj, dt);

    // 原始图中s到t的最短路长度
    int shortest_path_len = ds[t];
    
    // 计数器，用来记录有多少对合法的路口可以修路
    long long count = 0;

    // 开始枚举所有可能的路口对(i, j)
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            // 如果路已经存在了，就不能再修了，跳过！
            if (exists[i][j]) {
                continue;
            }

            // 这就是我们最重要的判断条件啦！
            // 新建(i, j)路后，s->i->j->t 和 s->j->i->t 两条新路径的长度
            // 都不能比原来的最短路短。
            if (ds[i] + dt[j] + 1 >= shortest_path_len && ds[j] + dt[i] + 1 >= shortest_path_len) {
                count++;
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(n^2 + m) 的说。
- 我们执行了两次 BFS。每次 BFS 的时间复杂度是 O(n + m)，其中 n 是节点数，m 是边数。所以两次是 O(2 * (n + m))。
- 之后，我们用了一个双重循环来枚举所有可能的节点对 (i, j)，这部分的复杂度是 O(n^2)。
- 所以总的时间复杂度就是 O(n + m + n^2)，在 n 比较大的时候，主要是 O(n^2) 占主导地位。对于这道题 n, m <= 1000，这个复杂度是完全可以接受的！
空间复杂度: O(n^2) 的说。
- 邻接表 adj 的空间是 O(n + m)。
- 两个距离数组 ds 和 dt 的空间都是 O(n)。
- exists 矩阵用来记录边是否存在，它的空间是 O(n^2)。
- 因此，空间开销最大的部分是 exists 矩阵，总空间复杂度是 O(n^2)。

知识点与总结

这道题真是一次愉快的思维体操呢，喵~ 从中我们可以学到不少东西：

BFS大法好: 对于无权图的最短路问题，BFS 是最直接、最高效的算法。一定要牢牢记住哦！
逆向思维与预处理: 解决问题的关键在于，我们不是真的去模拟每一次加边，而是分析加边会产生什么影响。通过预处理从起点 s 和终点 t 到所有点的距离，我们可以快速地对任意一条新边的影响做出判断。这种“正向跑一次，反向跑一次”的思路在很多图论问题中都非常有用！
组合数据结构: 代码里同时使用了邻接表和邻接矩阵（以 exists 数组的形式）。邻接表适合遍历一个点的所有邻居（BFS 中常用），而邻接矩阵适合快速查询两点间是否有边。根据不同需求选择合适的数据结构，能让代码更优雅高效。
枚举与检查: 当问题规模允许时，通过枚举所有可能性，并对每种可能性进行快速检查，是一种非常有效的暴力美学解法。这里的关键是，检查的步骤必须足够快，而这正是我们预处理的目的所在。

希望这篇题解能帮到你，主人！继续加油，算法的世界还有更多有趣的冒险等着我们去探索呢，喵~！

D. Fight Against Traffic - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​