首页 > 代码库 > hdu 4807 Lunch Time
hdu 4807 Lunch Time
转载自 http://blog.csdn.net/qq564690377/article/details/17100011
题意:在一个有向图当中,现在每一条边带有一个容量,现在有K个人在起点,需要到终点去吃饭,询问这K个人最后一个人到达食堂的最小时间是多少。
想法:联想到普通的网络流,那么我们网络流可以很轻松的求出两个点之间的最大容量是多少,但是现在的问题就是刚开始在起步的时候那么最开始的容量是不可能到达最大的,因为人还在途中,假设我们从时间角度来分析这个问题,再联想到我们网络流求法,费用流当中,求出来的就是当然费用最小(也就是路径长度最短)的增广路径,那么从这个时刻之后每个单位时间都有这么多人能够到达餐厅,然后我们在求费用流的过程中,把所有这样找到的增广路径处理掉,按时间递增,如果处理完之后还是没有到达人数,那么接下去每一个时刻到达的人数就是最大流流量,然后接下去的部分直接算出来就可以了,要特别注意k = 0 时的trick。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。