重要的城市

本题要求在一张无向加权图中寻找所有重要城市：若摧毁某节点会导致至少一对其他节点之间的最短路径变长或不可达，则称该节点为重要城市。

February 1, 2007题库1分钟阅读

参加 jsoi 冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。

同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi 冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。

他们认为这样的城市是重要的：如果一个城市 $c$ 被破坏后，存在两个不同的城市 $a$ 和 $b$ （ $a, b$ 均不等于 $c$ ）， $a$ 到 $b$ 的最短距离增长了（或不通），则城市 $c$ 是重要的。

jsoi 冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。

输入格式

第一行两个整数 $N,M,N$ 为城市数， $M$ 为道路数。

接下来 $M$ 行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度。

输出格式

一行，按递增次序输出若干的数，表示重要的城市。如果不存在这样的城市，请输出 No important cities.。

输入样例 1
4 4
1 2 1
2 3 1
4 1 2
4 3 2
输出样例 1
2
数据范围

对于 $30\%$ 的数据满足 $N\le 20$ ；

对于 $60\%$ 的数据满足 $N\le 100$ ；

对于 $100\%$ 的数据满足 $N\le 200,M\le \frac{N\times (N-1)}{2},0<c\le 10000$ 。 $c$ 即路的长度。

保证不出现重边和自环。

这道题的核心是找出图中的所有关键节点（重要城市）。

定义非常明确：如果城市 $c$ 被摧毁后，导致至少一对城市 $(a, b)$ 之间的最短路径变长（或无法到达），那么 $c$ 就是一个重要城市。

注意看数据范围： $N \le 200$ 。

$N$ 极小，这强烈暗示我们可以使用 $O(N^3)$ 的算法，最直接的手段就是 Floyd-Warshall 算法 来求解所有点对之间的最短路径。

假设在原图上， $a$ 到 $b$ 的最短距离为 $d[a][b]$ 。

必要条件：城市 $c$ 必须在 $a \to b$ 的某条最短路径上。即满足：

$d[a][c] + d[c][b] == d[a][b]$
充分条件：城市 $c$ 是 $a \to b$ 之间不可替代的关键节点（所有最短路都必须经过 $c$ ）。

若存在不经过 $c$ 的替代路径（如直连边或绕过 $c$ 的平行节点），长度同样等于 $d[a][b]$ ，则摧毁 $c$ 后， $a \to b$ 可以走替代路径，距离并不会增加。

使用 Floyd 算法 计算出任意两点 $i, j$ 之间的最短距离 $d[i][j]$ 。同时，用矩阵 $g[i][j]$ 记录原图的初始边权，用于后续判断直连边。

枚举每一个候选城市 $c \in [1, N]$ ，检查是否存在某对点 $(a, b)$ 使得 $c$ 是其最短路上的唯一必经点：

筛选处于最短路上的 $c$ ：遍历所有起点 $a$ 和终点 $b$ （满足 $a, b, c$ 两两不相等），检查是否满足：

$d[a][c] + d[c][b] == d[a][b]$
检查是否存在直连边替代：若 $g[a][b] == d[a][b]$ ，说明 $a \to b$ 存在不经过任何中间节点的直连最短路， $c$ 不是必经点，直接跳过。
检查是否存在平行节点 $k$ 替代：遍历其他节点 $k$ （ $k \neq a, b, c$ ），如果 $k$ 在 $a \to b$ 的最短路上（ $d[a][k] + d[k][b] == d[a][b]$ ），需进一步验证 $k$ 是否绕过了 $c$ ：
- 检查 $k$ 是否在 $c$ 前面（ $d[a][k] + d[k][c] == d[a][c]$ ）；
- 检查 $k$ 是否在 $c$ 后面（ $d[c][k] + d[k][b] == d[c][b]$ ）。
- 若 $k$ 既不在 $c$ 前也不在 $c$ 后，说明 $k$ 属于一条独立的平行最短路，即 $c$ 被成功绕过。
得出结论：若对于某对 $(a, b)$ ，不存在直连边且没有任何节点 $k$ 能绕过 $c$ ，则 $c$ 为重要城市，记录答案并继续检查下一个城市。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;
int d[205][205]; // 最短距离矩阵
int g[205][205]; // 原图边权矩阵（用于检测直连边）
int N, M;

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

    cin >> N >> M;

    // 初始化邻接矩阵与原图图结构
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i == j) {
                d[i][j] = 0;
                g[i][j] = 0;
            } else {
                d[i][j] = INF;
                g[i][j] = INF;
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = d[u][v];
        g[u][v] = d[u][v]; // 记录原图的边，防直连边干扰
        g[v][u] = d[v][u];
    }

    // 1. Floyd 算法求解任意两点最短路
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (d[i][k] < INF && d[k][j] < INF) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

    vector<int> important_cities;

    // 2. 枚举每个节点 c，判断其是否重要
    for (int c = 1; c <= N; ++c) {
        bool is_important = false;

        for (int a = 1; a <= N && !is_important; ++a) {
            if (a == c) continue;
            for (int b = 1; b <= N && !is_important; ++b) {
                if (b == c || a == b) continue;

                // 判断条件 1: c 是否在 a->b 的最短路上
                if (d[a][c] != INF && d[c][b] != INF && d[a][c] + d[c][b] == d[a][b]) {

                    // 如果 a->b 本身有直连边且边权等于最短路，
                    // 说明可以直接走直连边，完全不需要经过 c，c 绝非必经点
                    if (g[a][b] == d[a][b]) {
                        continue;
                    }

                    // 判断条件 2: 是否存在其他节点 k 能“绕过” c
                    bool has_alternative = false;
                    for (int k = 1; k <= N; ++k) {
                        if (k == a || k == b || k == c) continue;

                        // k 在 a->b 的最短路上
                        if (d[a][k] != INF && d[k][b] != INF && d[a][k] + d[k][b] == d[a][b]) {

                            // 检查 k 是否只是与 c 处于同一条路径上的前驱或后继（串联）
                            bool k_before_c = (d[a][k] + d[k][c] == d[a][c]); // k 在 c 前面 (a->k->c)
                            bool k_after_c  = (d[c][k] + d[k][b] == d[c][b]); // k 在 c 后面 (c->k->b)

                            // 只有当 k 既不在 c 前面，也不在 c 后面时，说明 k 走的是独立绕过 c 的平行路径！
                            if (!k_before_c && !k_after_c) {
                                has_alternative = true;
                                break;
                            }
                        }
                    }

                    // 如果既没有直连边替代，也没有平行节点替代，说明 c 是不可替代的！
                    if (!has_alternative) {
                        is_important = true;
                    }
                }
            }
        }

        if (is_important) {
            important_cities.push_back(c);
        }
    }

    // 3. 输出结果
    if (important_cities.empty()) {
        cout << "No important cities.\n";
    } else {
        for (size_t i = 0; i < important_cities.size(); ++i) {
            cout << important_cities[i] << (i + 1 == important_cities.size() ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

Floyd 预处理： $O(N^3)$ 。
重要性判定：理论上限为 $O(N^4)$ ，但由于极强的剪枝和约束（只有当 $c$ 在 $a \to b$ 的最短路上时才会去遍历 $k$ ；且一旦确定 $c$ 为重要城市，立刻 break 检查下一个城市），实际时间复杂度接近 $O(N^3)$ 。
运行表现：当 $N = 200$ 时，总计算量远小于 $10^8$ 次，能在 10~30ms 内轻松通过。

使用两个 $N \times N$ 的二维数组记录最短路距离 $d$ 与原图边权 $g$ ，空间复杂度为 $O(N^2)$ ，极省内存。