Zoj 1364 Poj 1325 Machine Schedule 二分图匹配 匈牙利算法 求点覆盖数等价于求匹配数

这题就是A机器有n 种模式,B机器有m种模式

一共有k件任务,每件任务既可在A机器的某个模式下完成,也可以在B机器的某个模式下完成。由于机器转换模式要重启,求重启的最少次数,两机器最初的模式是0

所以如果某任务可以在A机器或者B 机器的0模式下进行,这件任务就可以不考虑。把A,B机器的每个模式看成顶点。如果某任务可以在A机器的模式i 和B机器的模式j下完成,那么i和j 建一条边,该题可转换为找最小的顶点数,覆盖掉所有出现的边(相当于完成了所有的工作)。

而有定理,点覆盖数 = 匹配数,所以,把按如上方式构造出的图求一个最大匹配,其匹配数就是所求,记住去掉所有可以用0模式完成的工作(这些工作不用建边)。

原文地址:https://www.cnblogs.com/allh123/p/3011050.html