hdu 4807 Lunch Time
这也是个非常有趣的题。
有n个点，m条单向边，所有的边有一个流量限制，表示单位时间内只能通过那么多人。有K个人要从0点到n-1点，求最小时间，走过任意一条边的花费时间都为1。
这种模型肯定与网络流有关系。
如果从s到t就只有一条长度为d，流量为c的边。那么显然：从d时刻开始，每秒都会有c个人到达t点。
现在我们的问题就是把原网络拆成很多条这样的路径(d,c)。使得其效率最高。显然的是路径之间不会有任何影响。
可以注意到，路径的长度看起来是越短越优，越短就可以提前把人送到t点，就提醒到每次都要找尽可能短的增广路径，而这个就是最小费用流能解决的问题。在原图上跑最小费用流，每次增广一出一条路径，就把这条路径的属性(d,c)记下来，每次增广出来的d都是不下降的。这样就实现了把原网络分割成多条不相关路径的任务。
最后就可以愉快的二分答案，计算这个时间内能有多少人通过，与K比较，利用之前的推论。
也可以不二分答案，因为增广的过程中d是不降的，也可以想出来适当的方法来找出最小的时间通过K个人。
Written with StackEdit.