来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-time-when-the-network-becomes-idle

题目描述

给你一个有 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
解释：
0 秒最开始时，
- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
- 数据服务器 2 给主服务器发出信息（用 2A 表示）。

1 秒时，
- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。

2 秒时，
- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息（用 2C 表示）。
...
4 秒时，
- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
...
7 秒时，回复信息 2D 到达服务器 2 。

从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。

示例 2：

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3
解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。

提示：

n == patience.length
2 <= n <= 10⁵
patience[0] == 0
对于 1 <= i < n ，满足 1 <= patience[i] <= 10⁵
1 <= edges.length <= min(105, n * (n - 1) / 2)
edges[i].length == 2
0 <= ui, vi < n
u_i != v_i
不会有重边。
每个服务器都直接或间接与别的服务器相连。

解题思路

题目描述有点长。。总结一下就是每个服务器会向0号服务器发送信号，每个服务器需要收到0号回复后才结束发信号，否则每过patience[i]秒就重新发送信号，然后需要找到网络上完全没有信号的最早时间。

首先给的信息是网络的连接关系，可以先建立一张网络图，然后用广度优先遍历的方法找到每个服务器和0号服务器的最短路径Disp。

之后有两种情况：

当patience[i]比2 * Disp[i] 大时，服务器就发过一次信号，那么第i个服务器信号消失的时间就是2 * Disp[i] + 1。

当patience[i]比2*Disp[i]小时，服务器在收到回复前最后一次发信号时间是向下取整[(2 * Disp[i] - 1 ) / patience[i] ]* patience[i]。所以服务器信号消失的时间为向下取整[(2 * Disp[i] - 1 ) / patience[i] ]* patience[i] + 2 * Disp[i] + 1 可以看出，前一种情况是包含在这个里的，所以可以合并。

代码展示

class Solution {

public:

    int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {

        int n = patience.size(), iRet = 0;

        vector<vector<int>> vviMap(n);

        for(auto iter: edges)

        {

            vviMap[iter[0]].emplace_back(iter[1]);

            vviMap[iter[1]].emplace_back(iter[0]);

        }

        vector<int> viDisp(n, 0);

        queue<int> visiting;

        unordered_set<int> visited;

        visiting.push(0);

        while(!visiting.empty())

        {

            int iCur = visiting.front();

            visiting.pop();

            visited.insert(iCur);

            for(auto iter: vviMap[iCur])

            {

                if(visited.count(iter) == 0)

                {

                    visited.insert(iter);

                    viDisp[iter] = viDisp[iCur] + 1;

                    visiting.push(iter);

                }

            }

        }

        for(int i = 1 ; i < n; i++)

        {

            int iTemp = 2 * viDisp[i] + 1 +  (2 * viDisp[i] - 1) / patience[i] * patience[i];

            iRet = max(iRet, iTemp);

        }

        return iRet;

    }

};

巴特西

LeetCode-2039 网络空闲的时刻

题目描述

解题思路

代码展示

运行结果

最新文章

热门文章