从经典的AOV网、AOE网想到的问题 - swgr's Blog
从经典的AOV网、AOE网想到的问题
晚上煮点心吃的时候，突然想到一个问题。
----------------------我是混个陷----------------------
首先经典的工序问题的模型一般是，给出一个工程（比如做晚餐），包括工序之间的拓扑关系和每道工序所需要的时间。（比如洗米需要5min，洗锅需要3min，完成洗米、洗锅以后才能煮饭，煮饭需要30min...）
然后就可以在这个模型上做各种事了，譬如求一个可行的完成顺序（拓扑排序），或者求一个最短的完成时间（关键路径）等等。
----------------------还是混个陷----------------------
好吧，现在来说说我想到的问题。
在这个工序问题模型的基础上加入一个限制条件：同时进行的工序数不能超过m（可以理解为厨房一共有m个人在忙活）。显然，当m=1时，问题就变成了拓扑排序；当m=∞时，问题就变成了关键路径。
那么，当m不是1也不是无穷大时，如果想求工程的最短的完成时间，要如何做呢？
我还没有认真想这个问题的算法，我觉得某种类似关键路径的贪心方法可以做掉。
ACM_DIY群上有大牛无责任猜想是费用流做，不会网络流的菜鸟我表示压力很大。
----------------------就是混个陷----------------------
其实这里还涉及到一个如何把AOV网转成AOE网的问题。
以下是我无责任猜想的做法，不多说，直接上图。（鼠绘，渣技术，我自重）
2010年9月01日 17:11
果断路过打酱油。
2010年9月01日 19:36
@ftiasch: 郭神大驾光临，寒舍蓬荜生辉...
2010年10月28日 02:44
赞
2022年9月30日 01:03
General Science is one of the most important subjects to the Assam State SEBA board Government and Private school class 10th Grade. SEBA 10th Science Question Paper General Science is one of the most important subjects to the Assam State SEBA board Government and Private school class 10th Grade.Those students can download SEBA HSLC Science Study Material 2023 Pdf with an important question bank along suggested question bank for all science examination tests conducted by Secondary Education Board Assam.
2023年4月16日 15:49
In certain cases your mail may be exposed to public that Modelpapers works on giving out better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam model-paper.com and we try to protect every email as much as possible.