4 solutions

  • 0
    @ 2024-10-21 18:47:22

    题面描述:

    在一个公有云的网络中，有 NN 个网络节点可以用一个 n×nn \times n 的矩阵 matrix 表示，矩阵中的元素 matrix[i][j] = p 表示用户从节点 ii 访问节点 jj 时，必须在 ii 节点上具备至少 pp 的权限等级（当 p=0p = 0 时表示无法访问）。如果用户成功访问了 jj 节点，权限等级将提升为 pp。某些节点暴露在公网上，可能面临攻击风险，攻击者能够获取最大权限（等级为 10）。为了减小攻击可能带来的损失，网络安全工程师需要选择一个节点从公网下线，以便尽可能减少被攻击的节点数量 RR。若存在多个可选节点，优先选择索引最小的节点。输入包括网络节点数量 NN、一个 N×NN \times N 的矩阵，以及暴露节点的编号列表，输出应为下线的节点编号。

    dfs

    更优解有一个dijstra，基于这一题的数据范围考虑dfs，取所有情况的最优解，对于每一个可能暴露的节点，去尝试dfs(x,y,max)所有能攻击到的点，取能攻击最少数的点为答案，相同则取编号小的即可

    题解说明

    在这个问题中，我们需要通过选择一个暴露在公网的节点进行下线操作，以最小化被攻击的节点数量 RR。为了找到最佳的下线节点，我们可以使用深度优先搜索（DFS）策略来探索每个可能的情况。

    1. 输入处理：

      • 我们首先读取网络节点的数量 NN 和连接矩阵 matrix。
      • 然后，读取暴露在公网的节点列表。

    2. DFS 搜索：

      • 对于每一个暴露的节点，我们尝试将其下线，利用 BFS（广度优先搜索）来模拟攻击者从其他节点开始攻击的过程。
      • 在 BFS 中，我们会使用一个队列来管理当前可攻击的节点，并维护一个访问数组 vis，记录已经被攻击过的节点。
      • 攻击者从其他暴露节点开始，若当前节点具备足够的权限（即能够访问），则可以继续攻击其他节点，并提升权限等级。
      • 最后，统计未被攻击的节点数量，从而得到对应的 RR 值。

    3. 选择最优节点：

      • 对于每个暴露的节点，计算对应的未被攻击的节点数量，并记录最小的 RR 值及其对应的节点编号。如果有多个节点具有相同的攻击影响，则优先选择编号小的节点。

    4. 输出结果：

      • 输出选择下线的节点编号。

    代码如下

    cpp

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

int a[40][40]; // 存储权限矩阵
int n, m = 1; // n 为节点数量，m 为暴露节点的计数
int e[40]; // 存储暴露节点的编号
int vis[40]; // 访问数组，用于记录被攻击的节点

// DFS 模拟攻击过程
int dfs(int x) {
    queue<pair<int,int>> q; // 使用队列进行 BFS
    // 初始化访问状态
    for(int i = 0; i < n; i++) {
        vis[i] = 0; // 标记所有节点为未访问
    }
    // 将其他暴露节点入队（除去当前下线的节点 x）
    for(int i = 1; i <= m; i++) {
        if(i != x) {
            q.push({10, e[i]}); // 初始权限为 10
        }
    }
    // BFS 遍历
    while(!q.empty()) {
        auto [w, u] = q.front(); // 获取当前节点和权限
        q.pop();
        if(vis[u] == 1) { // 如果已经被访问过，跳过
            continue;
        }
        vis[u] = 1; // 标记为已访问
        // 遍历所有可能访问的节点
        for(int j = 0; j < n; j++) {
            // 如果当前权限足够且节点未被访问
            if(w >= a[u][j] && a[u][j] > 0 && vis[j] == 0) {
                q.push({a[u][j], j}); // 将可攻击的节点加入队列
            }
        }
    }
    // 统计未被攻击的节点数量
    int res = 0;
    for(int i = 0; i < n; i++) {
        if(vis[i] == 0) res++; // 计数未被攻击的节点
    }
    return res; // 返回未被攻击的节点数
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    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; // 最大未被攻击节点数量
    int id; // 最优下线节点的编号
    // 对每个暴露节点尝试下线
    for(int i = 1; i <= m; i++) {
        int now = dfs(i); // 计算当前情况下未被攻击的节点数量
        if(now > mx) { // 如果当前情况攻击的节点数量更多
            mx = now; // 更新最大值
            id = i; // 更新最优下线节点
        }
    }
    cout << e[id] << '\n'; // 输出下线节点的编号
}

    java

    import java.util.*;

public class Main {
    // 定义连接矩阵，最多支持 40 个节点
    static int[][] a = new int[40][40];
    static int n, m = 1; // n 为节点数量，m 为暴露节点的计数
    static int[] e = new int[40]; // 存储暴露节点的编号
    static boolean[] vis = new boolean[40]; // 访问数组，用于记录被攻击的节点

    // DFS 模拟攻击过程，参数 x 为当前下线的节点索引
    static int dfs(int x) {
        Queue<int[]> q = new LinkedList<>(); // 使用队列进行 BFS
        // 初始化访问状态
        for (int i = 0; i < n; i++) {
            vis[i] = false; // 标记所有节点为未访问
        }
        // 将其他暴露节点入队（除去当前下线的节点 x）
        for (int i = 1; i <= m; i++) {
            if (i != x) {
                q.offer(new int[]{10, e[i]}); // 初始权限为 10
            }
        }
        // BFS 遍历
        while (!q.isEmpty()) {
            int[] front = q.poll(); // 获取当前节点和权限
            int w = front[0], u = front[1];
            if (vis[u]) { // 如果已经被访问过，跳过
                continue;
            }
            vis[u] = true; // 标记为已访问
            // 遍历所有可能访问的节点
            for (int j = 0; j < n; j++) {
                // 如果当前权限足够且节点未被访问
                if (w >= a[u][j] && a[u][j] > 0 && !vis[j]) {
                    q.offer(new int[]{a[u][j], j}); // 将可攻击的节点加入队列
                }
            }
        }
        // 统计未被攻击的节点数量
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) 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); // 对暴露节点进行排序，忽略索引 0
        int mx = -1, id = 0; // mx 存储最大未被攻击节点数量，id 存储最优下线节点的索引
        // 对每个暴露节点尝试下线
        for (int i = 1; i <= m; i++) {
            int now = dfs(i); // 计算当前情况下未被攻击的节点数量
            if (now > mx) { // 如果当前情况攻击的节点数量更多
                mx = now; // 更新最大值
                id = i; // 更新最优下线节点
            }
        }
        System.out.println(e[id]); // 输出下线节点的编号
    }
}

    python

    import queue

# 输入节点数量
n = int(input())  
a = []  # 用于存储连接矩阵
# 读取连接矩阵
for i in range(n):
    row = list(map(int, input().split()))  # 读取每行并转换为整数列表
    a.append(row)  # 将行添加到矩阵中

# 读取暴露节点的编号
e = list(map(int, input().split()))  
e.sort()  # 对暴露节点进行排序

# 定义 DFS 函数，参数 x 为当前下线的节点索引
def dfs(x):
    q = queue.Queue()  # 创建队列用于 BFS
    vis = [0] * n  # 访问数组，初始化为 0，表示未访问
    
    # 将其他暴露节点入队（除去当前下线的节点 x）
    for i in range(len(e)):
        if i != x:
            q.put((10, e[i]))  # 初始权限为 10，入队暴露节点
    
    # BFS 遍历
    while not q.empty():
        w, u = q.get()  # 获取当前节点的权限和编号
        if vis[u] == 1:  # 如果该节点已被访问，跳过
            continue
        vis[u] = 1  # 标记该节点为已访问
        
        # 遍历所有可能访问的节点
        for j in range(n):
            # 如果当前权限足够且节点未被访问
            if w >= a[u][j] > 0 and vis[j] == 0:
                q.put((a[u][j], j))  # 将可攻击的节点加入队列

    # 统计未被攻击的节点数量
    res = sum(1 for i in vis if i == 0)  # 计算 vis 中为 0 的数量
    return res  # 返回未被攻击的节点数

mx = -1  # 初始化最大未被攻击节点数量
id = -1  # 初始化最优下线节点的索引
# 对每个暴露节点尝试下线
for i in range(len(e)):
    now = dfs(i)  # 计算当前情况下未被攻击的节点数量
    if now > mx:  # 如果当前情况攻击的节点数量更多
        mx = now  # 更新最大值
        id = i  # 更新最优下线节点索引

# 输出选择下线的节点编号
print(e[id])
    • 0
      @ 2024-9-19 18:59:09

      dfs

      更优解有一个dijstra，基于这一题的数据范围考虑dfs，取所有情况的最优解，对于每一个可能暴露的节点，去尝试dfs(x,y,max)所有能攻击到的点，取能攻击最少数的点为答案，相同则取编号小的即可

      代码如下

      cpp

      #include <bits/stdc++.h>
using namespace std;
int a[40][40];
int n,m=1;
int e[40];
int vis[40];
int dfs(int x){
	queue<pair<int,int>>q;
	for(int i=0;i<n;i++){
		vis[i]=0;
	}
	for(int i=1;i<=m;i++){
		if(i!=x){
			q.push({10,e[i]});
		}
	}
	while(q.size()>0){
		auto [w,u]=q.front();
		q.pop();
		if(vis[u]==1){
			continue;
		}
		vis[u]=1;
		for(int j=0;j<n;j++){
			if(w>=a[u][j]&&a[u][j]>0&vis[j]==0){
				q.push({a[u][j],j});
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
		if(vis[i]==0) res++;
	}
	return res;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	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;
	for(int i=1;i<=m;i++){
		int now=dfs(i);
		if(now>mx){
			mx=now;
			id=i;
		}
	}
	cout<<e[id]<<'\n';
}

      java

      import java.util.*;

public class Main {
    static int[][] a = new int[40][40];
    static int n, m = 1;
    static int[] e = new int[40];
    static boolean[] vis = new boolean[40];

    static int dfs(int x) {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            vis[i] = false;
        }
        for (int i = 1; i <= m; i++) {
            if (i != x) {
                q.offer(new int[]{10, e[i]});
            }
        }
        while (!q.isEmpty()) {
            int[] front = q.poll();
            int w = front[0], u = front[1];
            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            for (int j = 0; j < n; j++) {
                if (w >= a[u][j] && a[u][j] > 0 && !vis[j]) {
                    q.offer(new int[]{a[u][j], j});
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) 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 = 0;
        for (int i = 1; i <= m; i++) {
            int now = dfs(i);
            if (now > mx) {
                mx = now;
                id = i;
            }
        }
        System.out.println(e[id]);
    }
}

      python

      import queue

n = int(input())  
a = []
for i in range(n):
    row = list(map(int, input().split()))  
    a.append(row)

e = list(map(int, input().split()))  

e.sort()

def dfs(x):
    q = queue.Queue()
    vis = [0] * n  
    
    for i in range(len(e)):
        if i != x:
            q.put((10, e[i]))  
    
    while not q.empty():
        w, u = q.get()
        if vis[u] == 1:
            continue
        vis[u] = 1
        for j in range(n):
            if w >= a[u][j] > 0 and vis[j] == 0:
                q.put((a[u][j], j))
    
    res = sum(1 for i in vis if i == 0)
    return res

mx = -1
id = -1
for i in range(len(e)):
    now = dfs(i)
    if now > mx:
        mx = now
        id = i

print(e[id])
      • 0
        @ 2024-9-12 21:29:42 
        sys.setrecursionlimit(3000)
N = int(input())
mat = [[]*N for _ in range(N)]
for i in range(N):
    mat[i] = list(map(int,input().split()))
exposed = list(map(int,input().split()))
Rmin = float('inf')
delete_node = exposed[0]
def dfs(i,p,N):
    # i：当前所处节点  p：拥有的权限等级
    visited[i] = 1
    for j in range(N):  # 搜索当前节点可访问的所有节点
        # 若未访问过且能访问且拥有足够权限
        if j != i and visited[j]==0 and p >= mat[i][j] and mat[i][j] > 0:
            dfs(j,mat[i][j],N)
for i in range(len(exposed)):
    dn = exposed[i]
    visited = [0] * N
    expo = exposed[:i] + exposed[i+1:]  # 下线节点dn后，可从公网攻击的节点
    for n in expo:
        dfs(n,10,N)
    R = sum(visited)  # 要使R尽可能小
    if R < Rmin: Rmin,delete_node = R,dn
    elif R == Rmin and dn < delete_node: delete_node = dn
print(delete_node)
        • 0
          @ 2024-8-21 4:27:12

          思路

          考虑暴力dfs，先将暴露的节点按编号从小到大排序，考虑下线每个暴露的节点，下线之后从其它暴露节点开始dfs，赋予权限10，最后统计一下被攻击的节点数量。被攻击节点数量最少对应的下限节点就是答案。

          注意由于可能所有情况节点都会被攻击，所以幸存的节点数量初始化应该为-1。

          代码

          C++

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

int n,m;
int a[25][25];
int exposed[11];
int book[25],cnt[25];
int mx=-1,id;

void dfs(int x,int p){
        book[x]=true;
        cnt[x]++;
        for(int j=0;j<n;++j){
                if(a[x][j]&&!book[j]&&p>=a[x][j]){
                        dfs(j,min(p,a[x][j]));
                }
        }
}

void check(int x){
        for(int i=0;i<m;++i){
                if(exposed[i]==x) continue;
                memset(book,0,sizeof book);
                dfs(exposed[i],10);
        }
        int res=n;
        for(int i=0;i<n;++i){
                if(cnt[i]){
                        res--;
                }
        }
        if(res>mx){
                mx=res;
                id=x;
                
        }
}

int main(){
        //freopen("test.in","r",stdin);
        std::ios::sync_with_stdio(false);
        cin>>n;
        for(int i=0;i<n;++i){
                for(int j=0;j<n;++j){
                        cin>>a[i][j];
                }
        }
        while(cin>>exposed[m]){
                m++;
        }
        sort(exposed, exposed + m);
        for(int i=0;i<m;++i){
                memset(cnt,0,sizeof cnt);
                check(exposed[i]);
        }
        cout<<id;

        return 0;
}
          • @ 2024-9-18 23:24:26

            部分数据有误？题解只过9/15，并且测试点3似乎有误

        • 1

        2024.04.10-暑期实习-第三题-公网下线方案

        Information

        ID
        85
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        7
        Tags
        # Submissions
        226
        Accepted
        36
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 湘ICP备2023007293号
        3. Worker 0, 38ms
        4. Powered by Hydro v4.14.1 Community