输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

分析:这题是黑书上的例题(P325)我觉得很好……

这是网络流的一个类型,即动态流问题:题目要求的不是能送最多多少人,而是限定了流量,求最少需要多少时间。我们面临着难题,一般的流网络无法表示两点间不同时刻的不同容量和流量,因此我们要拆点。

如果最短时间是t,就把每个点Vi(包括源点和汇点)拆成Vi0,Vi1,Vi2,……,Vit这t+1个点,这样太空船在t-1时刻从vi出发在t时刻到达Vj就可以表示成Vit-1~~~Vjt,如果C(Vit-1,Vjt)=a,f(Vit-1,Vjt)=b则可以表示成太空船可以容纳a人,此时正载有b人;又因为每个太空站可以容纳无限的人停留,所以对于每个Vit-1都应有一条容量无限大的边指向Vit。源就是V00点,汇就是V-1t点,从源到汇的流量就表示到时刻T为止从地球到月球输送的总人数。至于T直接从小到大枚举就行,卡个时或者卡个T,超过就输出0

让我们来总结一下算法:

拆点
每次时间 T++,

然后每个节点(空间站,地球,火星)增加一个分点。
对于每次的T 由 第i个节点的T号分点 向第 i个节点的(T+1)号分点连一条容量无限的边   再由  第j艘飞船T时刻所在空间站的T号分点  向 第j飞船T+1时刻所在空间站的T+1号分点 连一条容量为h[j]的边
跑一遍sap k=k-ow
如果 k小于等于0 输出此刻的T
如果T大于100(数据比较弱,做下来运完的都在100以内) 输出0

05-11 13:47