题解思路与方法

建模

• 用一个 $N\times N$ 的邻接矩阵 matrix 表示节点间的访问授权门槛：
  • matrix[i][j]=p（p>0） 表示从节点 $i$ 到节点 $j$ 需要在节点 $i$ 上拥有至少 $p$ 级权限；
  • matrix[i][j]=0 表示不可访问。
• exposed 数组为所有直接暴露在公网的节点集合。若不下线某节点 $x$，攻击者可从所有其他暴露节点（初始权限为 10）发起多源 BFS/DFS，对可达节点进行“感染”。

算法

1. 枚举下线节点 $r\in exposed$：
   • 初始队列为所有 exposed 中除去 r 的节点，每个节点在队列中的初始权限为 10；
   • 对每个出队状态 $(u,perm_u)$ 遍历所有目标节点 $v$：
     • 若 matrix[u][v]>0 且 perm_u >= matrix[u][v]，则可访问；
     • 到达 $v$ 后，其权限变为 perm_v = matrix[u][v]；
     • 若之前到达 $v$ 时的权限小于 perm_v，则更新并将 $(v,perm_v)$ 入队。
   • BFS 结束后，统计所有被访问过的节点数 $R$。
2. 在所有候选 $r$ 中，选使 $R$ 最小的节点，若多个，取编号最小者。

这种做法相当于对带状态的图做多源最优 BFS，状态数上限为 $N\times 11$（权限等级 0–10）。

复杂度分析

• 枚举下线节点：最多 $|exposed|\le N$ 次；
• 每次 BFS 状态空间最多 $O(N\times P)$，其中 $P=11$ 为权限等级种类；
• 每个状态遍历 $N$ 条边，故单次 BFS 复杂度 $O(N\times P \times N)=O(N^2)$（常数 $P$ 可忽略）；
• 总体时间复杂度 $O(N^3)$，在 $N\le24$ 时远可接受。

代码

C++

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

int a[40][40]; // 存储权限矩阵
int n, m = 1;  // n 为节点数量，m 为暴露节点的计数（从 1 开始）
int e[40];     // 存储暴露节点的编号
int vis[40];   // 记录到达每个节点的最高权限，初始为 -1

// bfs 模拟攻击过程，返回“未被攻击”（安全）节点数
int bfs(int x) {
    queue<pair<int,int>> q; 
    // 初始化 vis 为 -1（未被攻击）
    for(int i = 0; i < n; i++) {
        vis[i] = -1;
    }
    // 多源入队：除去下线节点 x
    for(int i = 1; i <= m; i++) {
        if(i == x) continue;
        vis[e[i]] = 10;           // ROOT 权限
        q.push({e[i], 10});
    }
    // 带状态 BFS
    while(!q.empty()) {
        auto [u, p] = q.front(); q.pop();
        if(p < vis[u]) continue; // 已有更高权限到达过 u
        for(int j = 0; j < n; j++) {
            int req = a[u][j];
            if(req > 0 && p >= req && vis[j] < req) {
                vis[j] = req;
                q.push({j, req});
            }
        }
    }
    // 统计未被攻击的节点数
    int res = 0;
    for(int i = 0; i < n; i++) {
        if(vis[i] < 0) 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 >> a[i][j];

    // 读取暴露节点列表
    while(cin >> e[m]) m++;
    m--;
    sort(e + 1, e + m + 1);

    int mx = -1, id = 1;
    for(int i = 1; i <= m; i++) {
        int now = bfs(i);
        if(now > mx) {
            mx = now;
            id = i;
        }
    }
    cout << e[id] << "\n";
    return 0;
}

Java

import java.util.*;

public class Main {
    static int[][] a = new int[40][40];
    static int n, m = 1;      // m 从 1 开始计数
    static int[] e = new int[40];
    static int[] vis = new int[40]; // 记录到达每个节点的最高权限，初始为 -1

    // bfs 模拟攻击，返回安全节点数
    static int bfs(int x) {
        Queue<int[]> q = new ArrayDeque<>();
        // 初始化
        for (int i = 0; i < n; i++) vis[i] = -1;
        // 多源入队
        for (int i = 1; i <= m; i++) {
            if (i == x) continue;
            vis[e[i]] = 10;
            q.offer(new int[]{e[i], 10});
        }
        // 带状态 BFS
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int u = cur[0], p = cur[1];
            if (p < vis[u]) continue;
            for (int v = 0; v < n; v++) {
                int req = a[u][v];
                if (req > 0 && p >= req && vis[v] < req) {
                    vis[v] = req;
                    q.offer(new int[]{v, req});
                }
            }
        }
        // 统计未被攻击节点数
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (vis[i] < 0) res++;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = sc.nextInt();
        // 读取暴露节点
        while (sc.hasNextInt()) {
            e[m++] = sc.nextInt();
        }
        m--;
        Arrays.sort(e, 1, m + 1);

        int mx = -1, id = 1;
        for (int i = 1; i <= m; i++) {
            int now = bfs(i);
            if (now > mx) {
                mx = now;
                id = i;
            }
        }
        System.out.println(e[id]);
    }
}

Python

import queue

# 输入
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
e = list(map(int, input().split()))
e.sort()
m = len(e)

# bfs 模拟攻击，返回安全节点数
def bfs(x):
    q = queue.Queue()
    # vis 用作 “到达最高权限”，初始为 -1
    vis = [-1] * n
    for i in range(m):
        if i == x: continue
        vis[e[i]] = 10
        q.put((e[i], 10))
    while not q.empty():
        u, p = q.get()
        if p < vis[u]:
            continue
        for j in range(n):
            req = a[u][j]
            if req > 0 and p >= req and vis[j] < req:
                vis[j] = req
                q.put((j, req))
    # 未被攻击的节点数
    return sum(1 for v in vis if v < 0)

mx = -1
idx = 0
for i in range(m):
    now = bfs(i)
    if now > mx:
        mx = now
        idx = i

print(e[idx])

javascript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // 读入节点数
    let n = parseInt(await readline());
    // 初始化权限矩阵 a[n][n]
    let a = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        let row = (await readline()).split(/\s+/).map(Number);
        for (let j = 0; j < n; j++) {
            a[i][j] = row[j];
        }
    }

    // 读入并排序暴露节点列表 e
    let e = (await readline()).trim().split(/\s+/).map(Number).sort((x, y) => x - y);
    let m = e.length;

    // vis[i] 存储到达 i 时的最高权限，初始为 -1（未被攻击）
    let vis = Array(n).fill(-1);

    // 模拟下线 e[x] 后的 BFS 攻击，返回安全节点数
    function bfs(x) {
        // 重置 vis
        vis.fill(-1);
        let q = [];
        // 多源初始化，除去下线节点 x
        for (let i = 0; i < m; i++) {
            if (i === x) continue;
            vis[e[i]] = 10;       // ROOT 权限
            q.push([e[i], 10]);
        }
        // 带状态 BFS
        while (q.length) {
            let [u, p] = q.shift();
            // 如果当前权限不是最高，则跳过
            if (p < vis[u]) continue;
            // 遍历所有邻接节点
            for (let j = 0; j < n; j++) {
                let req = a[u][j];
                if (req > 0 && p >= req && vis[j] < req) {
                    vis[j] = req;
                    q.push([j, req]);
                }
            }
        }
        // 统计安全（未被攻击）节点数
        return vis.reduce((cnt, v) => cnt + (v < 0 ? 1 : 0), 0);
    }

    // 枚举每个暴露节点下线，选安全节点数最多者
    let mx = -1, best = 0;
    for (let i = 0; i < m; i++) {
        let safeCnt = bfs(i);
        if (safeCnt > mx) {
            mx = safeCnt;
            best = i;
        }
    }

    console.log(e[best]);
    rl.close();
})();

题目描述

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

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

小明是一名网络安全工程师，为了在有限的时间内尽可能的减少故障带来的损失，需要立即将某个节点从公网"下线"。

假设攻击结束时，被攻击过的节点数量为$R$，请帮小明计算出将哪个节点下线能使R尽可能小，如果答案有多个节点，返回索引最小的那个节点。请注意:从公网“下线”的节点，不会受到来自公网的攻击，但仍然可能被“可访问"的其他节点传递攻击。

输入描述

输入的第一行是网络节点数量$N$ 后续的$N$行，每行$N$个数字v，以空格分割，形成一个$N\times N$的矩阵，表示网络节点组网的矩阵。 最后一行，输入exposed数组，表示暴露在公网上的网络节点的编号列表数组元素不会重复。

$2\le N\le 24$

$0\le v\le 10$

$0\le exposed[i]\le N-1$

输出描述

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

样例1

输入

4
1 0 0 0
0 1 2 0
0 1 1 4
0 0 3 1
1 3

输出

3

说明

1,3是公网暴露的节点
1,2,3三个节点是连通的，但相互访问需要考虑权限等级限制，例如从1节点登录，访问到2节点后，权限等级不足以访问3号节点
如果将1号节点从公网下线，那3号节点可以先访问2号在访问1号，此时R的值为3。如果将3号节点从公网下线，则只能通过1号节点访问到2号节点，而2号节点无法再访问3号节点，此时R的值为2，答案选择R值更小的公网节点下线方案，因此答案为3.