信奥赛CSP-J复赛集训（图和树专题）（1）：P8604 [蓝桥杯 2013 国 C] 危险系数

信奥赛CSP-J复赛集训（图和树专题）（1）：P8604 [蓝桥杯 2013 国 C] 危险系数

题目背景

抗日战争时期，冀中平原的地道战曾发挥重要作用。

题目描述

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数 $DF(x,y)$：

对于两个站点 $x$ 和 $y(x\ne y),$ 如果能找到一个站点 $z$，当 $z$ 被敌人破坏后，$x$ 和 $y$ 不连通，那么我们称 $z$ 为关于 $x,y$ 的关键点。相应的，对于任意一对站点 $x$ 和 $y$，危险系数 $DF(x,y)$ 就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

输入格式

输入数据第一行包含 $2$ 个整数 $n(2\le n\le 1000)$，$m(0\le m\le 2000)$，分别代表站点数，通道数。

接下来 $m$ 行，每行两个整数 $u,v(1\le u,v\le n,u\ne v)$ 代表一条通道。

最后 $1$ 行，两个数 $u,v$，代表询问两点之间的危险系数 $DF(u,v)$。

输出格式

一个整数，如果询问的两点不连通则输出 $-1$。

输入输出样例 #1

输入 #1

7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

输出 #1

2

说明/提示

时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛

AC代码：

#include<bits/stdc++.h>
using namespace std;

int n, m;       // 站点数和通道数
int u, v;       // 询问的两个站点
int sum = 0;    // 记录从u到v的路径总数
int ans = 0;    // 记录危险系数（关键点数量）
int a[1010][1010];  // 邻接矩阵，a[i][j]=1表示站点i和j之间有通道
bool vis[1010];     // 标记数组，记录站点是否被访问过，避免重复访问
int cnt[1010];      // 记录每个站点在多少条路径中被经过（不含u和v）

// 深度优先搜索所有从x到v的路径，并统计路径中的站点
void dfs(int x) {
    if (x == v) {   // 到达目标站点v，找到一条路径
        sum++;      // 路径总数增加
        // 遍历所有站点，统计当前路径中经过的站点（排除u和v）
        for (int i = 1; i <= n; i++) {
            if (vis[i] && i != u && i != v) {
                cnt[i]++; // 站点i在这条路径中出现，计数增加
            }
        }
        return;
    }
    // 遍历所有可能的邻接站点
    for (int i = 1; i <= n; i++) {
        // 存在通道且未访问过
        if (a[x][i] == 1 && !vis[i]) {
            vis[i] = true;  // 标记为已访问
            dfs(i);         // 递归搜索下一站点
            vis[i] = false; // 回溯，恢复未访问状态
        }
    }
}

int main() {
    cin >> n >> m;
    // 初始化邻接矩阵
    for (int i = 1; i <= m; i++) {
        int u_tmp, v_tmp;
        cin >> u_tmp >> v_tmp;
        a[u_tmp][v_tmp] = 1;  // 无向图，双向标记
        a[v_tmp][u_tmp] = 1;
    }
    cin >> u >> v;    // 输入询问的起点和终点

    vis[u] = true;    // 起点u已访问
    dfs(u);           // 开始DFS搜索所有路径

    if (sum != 0) {   // 存在至少一条路径
        // 遍历所有站点，统计出现在所有路径中的站点
        for (int i = 1; i <= n; i++) {
            if (cnt[i] == sum) {  // 站点i出现在所有路径中
                ans++;
            }
        }
        cout << ans;
    } else {          // 无路径可达
        cout << -1;
    }
    return 0;
}

功能分析：

1. 问题目标：计算两个站点间的危险系数，即找出所有关键点。关键点的定义是：当该点被破坏后，两站点无法连通。
2. 算法思路：
   • DFS遍历所有简单路径：通过深度优先搜索遍历从起点u到终点v的所有简单路径（无重复节点）。
   • 统计路径中的站点：对于每条路径，记录路径中经过的所有站点（除u和v外）。若某站点出现在所有路径中，则为关键点。
3. 关键点判断：若某站点出现在所有路径中（cnt[i] == sum），则其为关键点。因为删除该点后，所有路径均被切断。
4. 复杂度问题：DFS的时间复杂度与路径数成指数关系。在极端情况下（如完全图），路径数可能爆炸式增长。但题目数据规模较小（n≤1000），且实际测试数据可能较友好，故能通过。
5. 邻接矩阵的适用性：使用邻接矩阵存储图结构，在稀疏图中效率较低。但本题m≤2000，邻接矩阵仍可接受。

文末彩蛋：

关注并查看老师的个人主页，学习完整csp信奥赛完整系列课程： https://edu.csdn.net/lecturer/7901