【BFS】2023Q1A-微服务的集成测试

题目描述与示例

题目描述

现在有 n 个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），其次服务自身启动加载会消耗一些时间。

给你一个 nxn 的二维矩阵 useTime，其中 useTime[i][i] = 10 表示服务 i 自身启动加载需要消耗 10s，useTime[i][j] = 1 表示服务 i 启动依赖服务 j 启动完成，useTime[i][k] = 0，表示服务 i 启动不依赖服务 k。存在0 <= i，j，k < n。

服务之间启动没有循环依赖（不会出现环），若想对任意一个服务 i 进行集成测试（服务 i 自身也需要加载），求最少需要等待多少时间。

输入描述

第一行输入服务总量 n，之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时 最后输入 k 表示计算需要等待多少时间后可以对服务 k 进行集成测试 其中 1 <= k <= n，1<=n<=100

输出描述

最少需要等待多少时间(s)后可以对服务 k 进行集成测试

示例一

输入

3
5 0 0
1 5 0
0 1 5
3

输出

15

说明

服务3 启动依赖服务2，服务 2 启动依赖服务 1，由于服务 1,2,3 自身加载需要消耗 5s，所以 5+5+5=15，需等待 15s 后可以对服务 3 进行集成测试

示例二

输入

3
5 0 0
1 10 1
1 0 11
2

输出

26

说明

服务 2 启动依赖服务 1 和服务 3，服务 3 启动需要依赖服务 1，服务 1,2,3 自身加载需要消耗 5s，10s，11s，所以 5+10+11=26，需等待 26s 后可以对服务 2 进行集成测试

示例三

输入

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

输出

12

说明

服务 3 启动依赖服务 1 和服务 2，服务 4 启动需要依赖服务 1,2,3，服务 1,2,3,4 自身加载需要消耗 2s，3s，4s，5s，所以 3+4+5=12s（因为服务 1 和服务 2 可以同时启动），需等待 12s 后可以对服务 4 进行集成测试

示例四

输入

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

输出

11

说明

服务 3 启动依赖服务 1 和服务 2，服务 4 启动需要依赖服务 1,2，服务 5 启动需要依赖服务 3,4，服务 1,2,3,4,5 自身加载需要消耗 1s，2s，3s，4s，5s，所以 2+4+5=11s（因为服务 1 和服务 2 可以同时启动，服务 3 和服务 4 可以同时启动），需等待 11s 后可以对服务 5 进行集成测试

解题思路

本题在常规的拓扑排序问题上加多了启动时间这一个限制条件，属于变形题。

代码

# 题目：2023Q1A-微服务的集成测试
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：拓扑排序BFS
# 代码看不懂的地方，请直接在群上提问

from collections import deque, defaultdict

# 输入节点数n
n = int(input())
# 输入关联矩阵
isConnected = list()
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

# 输入最后要查询的节点k，题目的索引是从1开始的，而我们储存数据的索引是从0开始的
# 故此处应该进行一个-1操作。譬如，服务4实际上是代码中的节点3。
k = int(input())-1

# 初始化入度数组，长度为n
inDegreeList = [0] * n

# 将关联矩阵isConnected转为熟悉的、方便操作的邻接表neighbor_table
neighbor_table = defaultdict(list)
for i in range(n):
    for j in range(n):
        # i依赖于j，要先运行了j才能运行i。注意此处i不能等于j
        if isConnected[i][j] == 1 and i != j:
            # 记录j的下一个邻接点包含i
            neighbor_table[j].append(i)
            # 同时i的入度+1
            inDegreeList[i] += 1


# 构建数组loadTimeList，储存每一个节点加载自身所需要的时间
loadTimeList = [isConnected[i][i] for i in range(n)]

# 初始化队列，用于维护BFS过程，起始搜索点为入度为0的节点
q = deque([i for i in range(n) if inDegreeList[i] == 0])

# 构建长度为n的时间数组totalTime，totalTime[i]表示第i个节点启动需要花费的总时间
totalTime = [0] * n

# 进行BFS
while len(q) > 0:
    # 弹出当前队头节点cur，说明cur是可以启动的
    cur = q.popleft()
    # cur节点启动的总时间，要加上其加载自身所需要的时间loadTimeList[cur]
    totalTime[cur] += loadTimeList[cur]
    # 如果发现弹出的节点cur就是所需要寻找的节点k，可以直接退出BFS循环，完成搜索
    # 注意这个判断条件可以不加
    if cur == k:
        break
    # 遍历所有cur的下一个运行节点nxt
    for nxt in neighbor_table[cur]:
        # nxt的入度减少1
        inDegreeList[nxt] -= 1
        # nxt的启动总时间，在未考虑nxt自身加载时间时，依赖于所有前置节点的启动时间，
        # 若出现前置节点totalTime[cur]启动总时间 > nxt启动总时间totalTime[nxt]
        # 则totalTime[nxt]需要以前置节点启动总时间为准
        totalTime[nxt] = max(totalTime[nxt], totalTime[cur])
        # 如果nxt的入度降为0，则可以加入队列中
        if inDegreeList[nxt] == 0:
            q.append(nxt)

# 输出totalTime[k]即为答案
print(totalTime[k])

时空复杂度

时间复杂度：O(N^2)。需要遍历整个isConnected关联矩阵。

空间复杂度：O(N^2)。邻接表neighbor_table所占空间最大为O(N^2)，其他变量所占空间最大为O(N)

，故总的空间复杂度为O(N^2)。