algorithm - swgr's Blog
从经典的AOV网、AOE网想到的问题
晚上煮点心吃的时候,突然想到一个问题。
----------------------我是混个陷----------------------
首先经典的工序问题的模型一般是,给出一个工程(比如做晚餐),包括工序之间的拓扑关系和每道工序所需要的时间。(比如洗米需要5min,洗锅需要3min,完成洗米、洗锅以后才能煮饭,煮饭需要30min...)
然后就可以在这个模型上做各种事了,譬如求一个可行的完成顺序(拓扑排序),或者求一个最短的完成时间(关键路径)等等。
----------------------还是混个陷----------------------
好吧,现在来说说我想到的问题。
在这个工序问题模型的基础上加入一个限制条件:同时进行的工序数不能超过m(可以理解为厨房一共有m个人在忙活)。显然,当m=1时,问题就变成了拓扑排序;当m=∞时,问题就变成了关键路径。
那么,当m不是1也不是无穷大时,如果想求工程的最短的完成时间,要如何做呢?
我还没有认真想这个问题的算法,我觉得某种类似关键路径的贪心方法可以做掉。
ACM_DIY群上有大牛无责任猜想是费用流做,不会网络流的菜鸟我表示压力很大。
----------------------就是混个陷----------------------
其实这里还涉及到一个如何把AOV网转成AOE网的问题。
以下是我无责任猜想的做法,不多说,直接上图。(鼠绘,渣技术,我自重)