题意分析

本题要求为一个绝密政府研究设施设计安全警卫部署方案。设施中房间通过单向气密门相连，所有客人从房间0进入，外星生物在指定房间（输入中给出）。为保护外星生物，需在通往该房间的路线上部署警卫（警卫不在关押外星生物的房间），且部署的房间需满足两个条件：一是客人到达外星生物房间必须经过该房间；二是不存在其他满足条件且更靠近外星生物房间的房间。输入包括房间数量、外星生物所在房间号以及一系列表示气密门连接关系的行，输出为部署警卫的房间号。

解题思路

1. 数据初始化：
   • 定义并初始化房间数量 n、外星生物所在房间号 m、邻接矩阵 graph（用于存储房间之间的连接关系）、访问标记数组 vis、自定义结构体数组 condi（用于存储每个房间的相关信息，如房间号 p、通过该房间的次数 time、到外星生物房间的距离 dis）。
   • 将 graph 初始化为全0，表示房间之间初始无连接；将 vis 初始化为全0，表示所有房间未被访问；将 condi 数组中每个元素的 dis 设为极大值 INF，time 设为0，p 设为房间编号。
2. 构建邻接关系：根据输入的气密门连接关系，更新邻接矩阵 graph，graph[v][u] = 1 表示存在从房间 u 到房间 v 的单向连接。
3. 深度优先搜索（DFS）：从外星生物所在房间 m 开始进行深度优先搜索，标记访问过的房间，计算每个房间被经过的次数 time。如果到达房间0，则将房间0的 time 加1，返回1；否则遍历相邻未访问且有连接的房间，递归调用 dfs，累加返回值，并在递归结束后撤销房间访问标记。
4. 广度优先搜索（BFS）：从外星生物所在房间 m 开始进行广度优先搜索，标记访问过的房间，计算每个房间到外星生物房间的距离 dis。将起始房间的 dis 设为0，加入队列，当队列不为空时，取出队首房间，遍历其相邻未访问且有连接的房间，更新其 dis 并加入队列。
5. 确定警卫部署房间：将外星生物所在房间的 dis 设为极大值 INF（因为警卫不部署在该房间），按照 time 从大到小、dis 从小到大的顺序对 condi 数组进行排序，输出排序后第一个房间的编号，即为部署警卫的房间。

复杂度分析

1. 时间复杂度：
   • 初始化部分：初始化邻接矩阵 graph 的时间复杂度为 $O(n^2)$，初始化访问标记数组 vis 和 condi 数组的时间复杂度均为 $O(n)$，总体初始化时间复杂度为 $O(n^2 + 2n) = O(n^2)$。
   • 构建邻接关系部分：根据输入构建邻接矩阵，假设输入的连接关系有 e 条，时间复杂度为 $O(e)$。
   • 深度优先搜索部分：最坏情况下，每个房间都被访问一次，且每个房间的相邻房间也都被访问，时间复杂度为 $O(n^2)$（因为对于每个房间，最多需要遍历 n 个相邻房间）。
   • 广度优先搜索部分：每个房间最多入队和出队一次，对于每个房间，最多遍历 n 个相邻房间，时间复杂度为 $O(n^2)$。
   • 排序部分：对 condi 数组进行排序，使用 sort 函数，时间复杂度为 $O(n \log n)$。
   • 总体时间复杂度为 $O(n^2 + e + n^2 + n^2 + n \log n) = O(n^2 + e)$，因为 $e$ 最大为 $n^2$，所以总体时间复杂度为 $O(n^2)$。
2. 空间复杂度：
   • 邻接矩阵 graph 占用的空间为 $O(n^2)$。
   • 访问标记数组 vis、visitTime 数组、距离数组 dis 以及 condi 数组占用的空间均为 $O(n)$，总体空间复杂度为 $O(n^2 + 4n) = O(n^2)$。

代码实现

#include<iostream>
#include<cstdio>
#include<string.h>
#include<iomanip>
#include<queue>
#include<algorithm>
#define INF 0x3fffffff
using namespace std;
const int N = 20;

int n, m;
int graph[N][N];
int vis[N];
int visitTime[N]; 
int dis[N];

struct node {
    int p;
    int time;
    int dis;
} condi[N];

// 比较函数，用于对condi数组进行排序
int cmp(node a, node b) {
    if (a.time == b.time)
        return a.dis < b.dis;
    return a.time > b.time;
}

// 深度优先搜索函数
int dfs(int cur) {
    int ok = 0;
    if (cur == 0) {
        condi[0].time++;
        return 1;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i] && graph[cur][i]) {
            vis[i] = 1;
            ok += dfs(i);
            vis[i] = 0;
        }
    }
    condi[cur].time += ok;
    return ok;
}

// 广度优先搜索函数
void bfs(int cur) {
    for (int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    condi[cur].dis = 0;
    queue<int> q;
    q.push(cur);
    vis[cur] = 1;
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (graph[pos][i] &&!vis[i]) {
                vis[i] = 1;
                condi[i].dis = condi[pos].dis + 1;
                q.push(i);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }
    // 初始化访问标记数组
    for (int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    // 初始化condi数组
    for (int i = 0; i < n; i++) {
        condi[i].dis = INF;
        condi[i].time = 0;
        condi[i].p = i;
    }
    // 构建邻接关系
    while (scanf("%d%d", &u, &v)!= EOF) {
        graph[v][u] = 1;
    }
    vis[m] = 1;
    dfs(m);
    bfs(m);
    // 将外星生物所在房间的dis设为极大值
    condi[m].dis = INF;
    // 对condi数组进行排序
    sort(condi, condi + n, cmp);
    // 输出部署警卫的房间号
    printf("Put guards in room %d.\n", condi[0].p);

    return 0;
}