机试题公网下线方案

2025-03-09 约 1510 字预计阅读 4 分钟

https://bing.ee123.net/img/rand?artid=146135042

机试题——公网下线方案

题目描述

公有云的某个region内， N 个网络节点组网情况可以使用一个 N×N 的矩阵 matrix 表示。在这个组网图中， matrix[i][j] = p 时，表示用户在编号为 i 的节点访问编号为 j 的节点时，必须在 i 节点上具有 ≥p 的权限等级（ p=0 时表示无法通过 i 节点访问 j 节点）。如果用户成功访问了 j 节点，那么它在 j 节点上的权限等级调整为 p 。

exposed 为一个整数数组，表示暴露在公网上的网络节点的编号列表。某天扫描发现这批暴露在公网的节点存在被外部恶意攻击风险，且该攻击会影响到可访问的其他节点，并可以持续传递进行攻击。被恶意攻击的节点从公网访问时，攻击者获得了ROOT权限（权限等级为10，即最大值）。

小明是一名网络安全工程师，为了在有限的时间内尽可能减少故障带来的损失，需要立即将某个节点从公网“下线”。假设攻击结束时，被攻击过的节点数量为 R ，请帮小明计算出将哪个节点下线能使 R 尽可能小。如果答案有多个节点，返回索引最小的那个节点。请注意：从公网“下线”的节点，不会受到来自公网的攻击，但仍然可能被“可访问”的其他节点传递攻击。

输入描述

第一行：一个整数 N ，表示网络节点数量（ 2 ≤ N ≤ 24 ）。
接下来 N 行：每行 N 个数字 v ，以空格分割，形成一个 N×N 的矩阵，表示网络节点组网的矩阵（ 0 ≤ v ≤ 10 ）。
最后一行：输入 exposed 数组，表示暴露在公网上的网络节点的编号列表，数组元素不会重复（ 0 ≤ exposed[i] ≤ N-1 ）。

输出描述

输出在 exposed 数组中，计划“下线”的那个节点的编号。

用例输入

1 和 3 是公网暴露的节点。
1 、 2 、 3 三个节点是连通的，但相互访问需要考虑权限等级限制。
例如从 1 节点登录，访问到 2 节点后，权限等级不足以访问 3 号节点。
如果将 1 号节点从公网下线，那 3 号节点可以先访问 2 号再访问 1 号，此时 R 的值为 3 。
如果将 3 号节点从公网下线，则只能通过 1 号节点访问到 2 号节点。

解题思路

问题建模 ：
- 该问题可以看作是一个 图论问题 ，目标是找到一个节点，将其从公网下线后，被攻击的节点数量 R 最小。
- 使用优先队列（大顶堆）模拟攻击过程，从权限等级高的节点开始传播攻击。
数据结构 ：
- 使用二维数组 mp 存储网络节点组网的矩阵。
- 使用 vector<int> 存储暴露在公网上的节点编号 exposed 。
- 使用 vector<int> 存储每个节点的最大权限等级 vis 。
- 使用优先队列 priority_queue 模拟攻击传播过程。
模拟攻击传播 ：
- 对于每个暴露的节点，如果该节点不是被下线的节点，则将其加入优先队列。
- 从优先队列中取出当前节点，尝试访问其所有可达的节点。
- 如果当前节点的权限等级足够访问目标节点，则将目标节点加入优先队列，并更新目标节点的最大权限等级。
计算被攻击的节点数量 ：
- 遍历所有节点，统计被攻击的节点数量 R 。
选择最优节点 ：
- 遍历所有暴露的节点，计算每个节点下线后的被攻击节点数量 R 。
- 选择使 R 最小的节点，如果有多个节点使 R 最小，则选择索引最小的节点。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
#include<iomanip>
#include<cstdint>
using namespace std;

int mp[25][25]; // 存储网络节点组网的矩阵
int n; // 网络节点数量
vector<int> exposed; // 暴露在公网上的网络节点编号

// 屏蔽掉root之后可以入侵的数量
int getr(int root) {
    // 权限 节点编号
    priority_queue<pair<int, int>> q;
    // vis节点可以获得的最大权限
    vector<int> vis(n, -1);
    // 从权限大的节点开始更新
    for (int i = 0; i < exposed.size(); i++) {
        if (exposed[i] == root) continue;
        else {
            vis[exposed[i]] = 0; // 初始节点
            q.push({0, exposed[i]});
        }
    }
    while (!q.empty()) {
        int cur_v = q.top().first;
        int cur_node = q.top().second;
        q.pop();
        for (int i = 0; i < n; i++) {
            int ne_node = i;
            int ne_v = mp[cur_node][ne_node];
            if (vis[ne_node] >= 0) continue; // 有权限大的更新过了
            if (ne_v) {
                // 可以访问到，判断权值是否足够
                if (cur_v == 0 || cur_v >= ne_v) {
                    // 初始节点或者当前权值足够
                    vis[ne_node] = ne_v;
                    q.push({ne_v, ne_node});
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i] != -1) res++;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mp[i][j];
        }
    }
    int value;
    while (cin >> value) {
        exposed.push_back(value);
    }
    int minn = INT_MAX;
    int minn_index = INT_MAX;
    for (int i = 0; i < exposed.size(); i++) {
        int temp = getr(exposed[i]);
        if (temp < minn) {
            minn = temp;
            minn_index = exposed[i];
        } else if (temp == minn) {
            minn_index = min(minn_index, exposed[i]);
        }
    }
    cout << minn_index;
    return 0;
}