[BZOJ3931/Luogu3171][CQOI2015]网络吞吐量(网络流,最短路)

发布于 2018-03-20  7 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3931/Luogu3171][CQOI2015]网络吞吐量(网络流,最短路)

Description

路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中,路由器会使用经典的Dijkstra算法计算最短路径,然后尽量沿最短路径转发数据包。现在,若已知一个计算机网络中各路由器间的连接情况,以及各个路由器的最大吞吐量(即每秒能转发的数据包数量),假设所有数据包一定沿最短路径转发,试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销,不考虑链路的带宽限制,即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点,自身的吞吐量不用考虑,网络上也不存在将1和n直接相连的链路。

Http

BZOJ
Luogu

Tag

网络流,最短路

解决思路

先走出最短路,求出最短路图,保证上面的每一条边的转移都是在最短路上转移,然后求最大流即可。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3931/Luogu3171][CQOI2015]网络吞吐量(网络流,最短路)


HNCJ OIer 一枚