最小点覆盖问题详解

男娘i 2022-08-01 06:09 197阅读 0赞

那么一如既往，还是个人觉得学习某一个知识点之前先粗俗的了解其是个什么东东，然后再去了解概念比较好...那么下面结合题目来了解：

首先最最重要的是理解题意，有k个任务，每个任务task\_i可以用机器A的x\_i模式做，也可以由机器B的y\_i模式做(值得注意的是只有两个机器，但是有不同的模式，每次可以在一个模式下工作),在做所有的任务之前，A与B的模式都最开始调为0，为了把所有任务做完，我们需要按照不同的任务，调制机器A或者B的模式，那么，我们最少要调制机器多少次，能完成所有的任务？  
**比如**，  
任务task\_0要么由A的模式0完成，要么由B的模式1完成，  
任务task\_1要么由A的模式1完成，要么由B的模式0完成，  
那么我们要调整机器多少次呢？  
首先机器的模式都是0（再次说明题目中最开始的模式是0），用A的0先完成task\_0，用B的0完成task\_1就可以啦...所以，我们一次都不用调制  
但是如果还有几个个任务  
task\_2要用A的1模式，或者B的2模式，  
task\_3要么由A的2模式要么B的2模式完成    ..你要调制机器几次呢？  
可以有以下几个方案：  
1.调制A从0到1，完成task\_2，然后调制A从1到2，完成task\_3---总共调制2次  
2.调制A从0到1，完成task\_2，然后调制B从0到2，完成task\_3---总共调制也是2次  
3.调制B从0到2，那么就可以同时完成task2,task\_3,-----------总共调制1次

到这里，题目都差不多描述完啦，那么下面就是粗俗了解”最小点覆盖“这个新东西，并且如何将其和题目结合

1.首先画图来理解“最小点覆盖”，就拿我们上面的例子来说，(先不管最小点覆盖这个概念)最开始把task和机器联系起来(就是task\_i能给哪个机器的哪个模式做就连一条线),联系起来之后便是如下:

![Center][]从图中看，结合最开始的题意理解,可以知道task0和1都让A的0模式做，task2,3都让B的模式2去做可以达到题目要求：最少调整机器的次数，现在我们就把要做的工作当做联系A、B机器的线(从图中看得出每一个任务把机器的模式连接起来)，简化为下图：

![Center 1][]那么现在我们A的0模式邻接了2条边，B的2模式邻接了2条边，我们知道边就是任务，图中的圆圈就是机器的模式，那么现在就题目就成了我们选最少的点(机器模式)，可以邻接更多的线(任务),那么我们把邻接叫做覆盖，也就是说成了选最少的点，去覆盖尽可能多的边.....**嘿嘿，是不是觉得"最小点覆盖"有那么点概念了呢？**

那么根据公式 ：最小点覆盖=最大匹配 如果想知道为啥，推荐一个:[最小点覆盖证明][Link 1]

[Center]: /images/20220731/087fe364a3504b1daa10fe5c5bb8f68c.png
[Center 1]: /images/20220731/ef0f76eafc0a4a24938ce2cf8ff590e4.png
[Link 1]: http://www.cnblogs.com/g0feng/archive/2012/11/05/2755713.html