分类:
2009-09-26 14:12:41
题意:
有两台机器A和B,分别有n种和m种不同的模式,有k个工作,每个工作都可以在那两个机器的某种特定的模式下处理。如job0既可以在A机器的3好模式下处理,也可以在B机器的4号模式下处理。
机器的工作模式改变只能通过人工来重启。通过改变工作的顺序,和分配每个工作给合适的机器可以减少重启机器的次数达到最小。任务就是计算那个最小的次数。初始时两台机器都运行在0号模式下。
思路:
把每个任务化为一条线,假设任务i在A机器上处理的模式为A[x]点,在B机器上为B[y]点,连接A[x]和B[y],用A机器和B机器中最少的点覆盖所有的边(用最少的模式完成所有的任务)。这是最小点覆盖问题,根据König定理(一个二分图中的最大匹配数等于这个图中的最小点覆盖数)就是求的二分图的最大匹配,然后再用匈牙利算法直接就算出最大匹配数了,要注意的是初始是在0号模式下,所以如果A或B机器其中至少有个在0号模式下时就不用重启机器了,所以建图的时候没有把0建进去。
关于二分匹配在http://blog.chinaunix.net/u3/102624/showart.php?id=2060232
|