Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

09/24
09:33
dijkstra 最大流

[bzoj 3931] [CQOI2015]网络吞吐量

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入文件第一行包含两个空格分开的正整数n和m,分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行,每行包含三个空格分开的正整数a、b和d,表示从路由器a到路由器b存在一条距离为d的双向链路。 接下来n行,每行包含一个正整数c,分别给出每一个路由器的吞吐量。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一个整数,为题目所求吞吐量。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

70

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于100%的数据,n≤500,m≤100000,d,c≤10^9

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

题意即题解,先跑一遍最短路,然后建图,再跑一遍最大流,没了

c++:

pascal:

 

[bzoj 3931] [CQOI2015]网络吞吐量