2039. 网络空闲的时刻

Medium

题目描述

有 n 个服务器，编号为 0 到 n - 1。给你一个二维整数数组 edges，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息通道，它们可以在一秒内直接相互传递任意数量的信息。同时给你一个长度为 n 且下标从 0 开始的整数数组 patience。

所有服务器都是相连的，也就是说，可以通过信息通道直接或间接地从一个服务器向任何其他服务器传递信息。

编号为 0 的服务器是主服务器，其余的都是数据服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按最优路线传递，也就是说每条信息都会以最少的时间到达主服务器。主服务器会立即处理所有新到达的信息并立即通过原路返回回复信息。

在第 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每一秒的开始，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新到达的回复信息）：

如果还没收到任何回复，那么该服务器会周期性地重发信息。数据服务器 i 每 patience[i] 秒重发一条信息，也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒后会重发一条信息。
否则，该数据服务器不会再重发信息。

当没有任何信息在服务器间传递或到达服务器时，网络变为空闲状态。

请返回网络变为空闲状态的最早秒数。

示例 1：

输入：edges = [[0,1],[1,2]], patience = [0,2,1]
输出：8

示例 2：

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3

提示：

n == patience.length
2 <= n <= 10^5
patience[0] == 0
1 <= patience[i] <= 10^5 for 1 <= i < n
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= ui, vi < n
ui != vi
没有重复的边
每个服务器都可以直接或间接地到达另一个服务器

解题思路

这道题的核心是理解消息的发送和接收机制，然后计算网络空闲的时间。

解题思路：

计算最短距离：首先使用BFS求出每个数据服务器到主服务器（编号0）的最短距离。这决定了往返时间。
分析消息流程：
- 每个数据服务器在第0秒发送第一条消息
- 消息到达主服务器需要 dist 秒，回复也需要 dist 秒，总往返时间为 2 * dist
- 如果在收到第一个回复前，服务器会每隔 patience[i] 秒重发消息
计算重发次数：对于服务器 i，在第一个回复到达前（即在 2 * dist[i] 秒内），它会发送的消息总数为：
```
totalMessages = 1 + (2 * dist[i] - 1) / patience[i]
```
这里减1是因为在第 2 * dist[i] 秒时就收到回复了，不会再重发。
计算最后一条消息的回复时间：
- 最后一条消息在第 (totalMessages - 1) * patience[i] 秒发送
- 它的回复在第 (totalMessages - 1) * patience[i] + 2 * dist[i] 秒到达
求最大值：网络空闲时间就是所有服务器最后收到回复的时间中的最大值加1。

代码实现

class Solution {
public:
    int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
        int n = patience.size();
        
        // 构建邻接表
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        // BFS求最短距离
        vector<int> dist(n, -1);
        queue<int> q;
        q.push(0);
        dist[0] = 0;
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            for (int neighbor : graph[node]) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    q.push(neighbor);
                }
            }
        }
        
        int maxTime = 0;
        
        // 计算每个数据服务器的最后回复时间
        for (int i = 1; i < n; i++) {
            int roundTrip = 2 * dist[i];
            int totalMessages = 1 + (roundTrip - 1) / patience[i];
            int lastSendTime = (totalMessages - 1) * patience[i];
            int lastReplyTime = lastSendTime + roundTrip;
            maxTime = max(maxTime, lastReplyTime);
        }
        
        return maxTime + 1;
    }
};

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        
        # 构建邻接表
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # BFS求最短距离
        dist = [-1] * n
        queue = deque([0])
        dist[0] = 0
        
        while queue:
            node = queue.popleft()
            
            for neighbor in graph[node]:
                if dist[neighbor] == -1:
                    dist[neighbor] = dist[node] + 1
                    queue.append(neighbor)
        
        max_time = 0
        
        # 计算每个数据服务器的最后回复时间
        for i in range(1, n):
            round_trip = 2 * dist[i]
            total_messages = 1 + (round_trip - 1) // patience[i]
            last_send_time = (total_messages - 1) * patience[i]
            last_reply_time = last_send_time + round_trip
            max_time = max(max_time, last_reply_time)
        
        return max_time + 1

public class Solution {
    public int NetworkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.Length;
        
        // 构建邻接表
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        // BFS求最短距离
        int[] dist = new int[n];
        Array.Fill(dist, -1);
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        dist[0] = 0;
        
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            
            foreach (int neighbor in graph[node]) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        int maxTime = 0;
        
        // 计算每个数据服务器的最后回复时间
        for (int i = 1; i < n; i++) {
            int roundTrip = 2 * dist[i];
            int totalMessages = 1 + (roundTrip - 1) / patience[i];
            int lastSendTime = (totalMessages - 1) * patience[i];
            int lastReplyTime = lastSendTime + roundTrip;
            maxTime = Math.Max(maxTime, lastReplyTime);
        }
        
        return maxTime + 1;
    }
}

var networkBecomesIdle = function(edges, patience) {
    const n = patience.length;
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const distances = Array(n).fill(-1);
    const queue = [0];
    distances[0] = 0;
    
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (distances[neighbor] === -1) {
                distances[neighbor] = distances[node] + 1;
                queue.push(neighbor);
            }
        }
    }
    
    let maxTime = 0;
    
    for (let i = 1; i < n; i++) {
        const roundTrip = 2 * distances[i];
        const lastResend = Math.max(0, Math.floor((roundTrip - 1) / patience[i]) * patience[i]);
        const lastReplyTime = lastResend + roundTrip;
        maxTime = Math.max(maxTime, lastReplyTime);
    }
    
    return maxTime + 1;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(V + E)，其中V是顶点数（服务器数），E是边数。BFS遍历所有节点和边各一次
空间复杂度	O(V + E)，用于存储图的邻接表和BFS的距离数组

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目