约翰农场的牛奶输送网络由 条管道()组成,这些管道用于将牛奶从牛棚输送到牛奶储存罐。他计划在未来一年内移除并更新大部分管道,但希望保留一条完整的管道路径,以便仍能将牛奶从牛棚输送到储存罐。
该管道网络由 个连接点()描述,每个连接点可以作为一组管道的端点。连接点 是牛棚,连接点 是储存罐。每条双向管道连接一对连接点,并具有相关的延迟(牛奶从管道一端到达另一端所需的时间)和容量(在稳定状态下每单位时间可以通过管道输送的牛奶量)。同一对连接点之间可以有多条管道连接。
对于从牛棚到储存罐的管道路径,路径的延迟是路径上各管道延迟的总和,路径的容量是路径上各管道容量的最小值(因为这是限制牛奶通过路径的整体速率的「瓶颈」)。如果约翰想通过一条延迟为 、容量为 的管道路径输送总量为 的牛奶,则所需时间为 。
给定约翰的管道网络结构,请帮助他选择一条从牛棚到储存罐的路径,使他能够在最短的总时间内输送 单位的牛奶。