poj 1325Machine Schedule解题报告-最小顶点覆盖等于最大匹配数

题目链接：

题目描述：2台机器A和B，分别有n，m种工作状态，k个工作，可以在A机器x状态下工作，也可以在B机器y状态下工作。问最少切换多少次机器状态可以完成所有工作。

解题思路：把A机器下的工作状态看作点集X，B机器下的每个工作状态看作点集Y，每个任务i看做一条连接状态a[x]和b[y]的边，问题转化为求解最少的点覆盖（关联）每一条边。

此问题也是最小顶点覆盖问题，并且有一个定理，估计大家也很熟悉：

König定理：二分图中的最大匹配数等于这个图中的最小顶点覆盖数。

设二分图的最大匹配数为M，证明如下：（来自黑书）

1) M个是足够的。形成最大匹配的M条边上对应的顶点一定会覆盖所有的边，否则，若有边没有被覆盖，把这条边加入，得到更大的匹配；

2) M个是必需的（最小的）。仅考虑形成最大匹配的M条边，由于它们两两之间没有公共的顶点，因此至少需要M个点才能把他们覆盖（若减去一个任意匹配边e上的点，则e没有被覆盖）。

证明完毕。

顺便，这位Matrix67大牛的博客也有一个证明，表示看的不是很明白，大家去研究吧。

 

有了这个定理，再加上匈牙利算法的模板，就差不多了，还有一点注意的是：当 x = 0 或者 y = 0 时， 这不需要连边，原因是该任务要在起始状态工作，则不需要切换状态。

 

代码如下，邻接矩阵实现：