Gravatar
yuan
积分:1076
提交:413 / 669

Pro282  [NOI 1998]SERNET模拟

思路:

    求出每个数据包在网络中存在的最(晚)后时刻,不妨记作 $last$,则 $last>T$ 的数据包数即是答案。

要点:

    1、对于被复制的某数据包,服务器 $i$ 只会转发最早且第一次到达自己的那个复制包,因为后续到达的相同数据包将会被接收而不再转发;

    2、最早到达服务器 $i$ 的复制包一定是通过最短路(最少传输时间)抵达的,然后通过服务器 $i$ 的最长出边转发出去的复制包可能会在网络中存在更久;

    3、那么,对于服务器 $i$ 而言,某数据包传输过程分为两段:(1)从起点 $s$ 沿最短路抵达服务器 $i$;(2)沿服务器 $i$ 最长边转发至邻接服务器;

    则:某数据包传输时间 $=$ $shortest[i]$ $+$ $farest[i]$,前者是从 $s \sim i$ 的最短路,后者是 $i$ 的最长出边;

    

    综上,$last = max\{ shortest[i] + farest[i] \} + startime$(开始传输时刻) 


2022-09-22 00:19:08    
我有话要说
暂无人分享评论!