poj 1325 Machine Schedule(二分图的最小顶点覆盖,匈牙利算法)

2016年5月26日 0 作者 CrazyKK

poj 1325 题目链接
题意:有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组(i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启,问最少的重启次数。

 

思路:这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。

完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。

 

然后这道题就变成了二分图的最小顶点覆盖。

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

根据Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

一个证明:二分图最小顶点覆盖的证明

 

剩下的就是裸的hungary..

然而WA了好几次。。。

一个小细节没处理好。。。

由于初始是模式0.。。

所以模式0肯定要特殊考虑。。。因为初始状态是没有重启的。。。

但是我错误得以为只有当存在(i,0,0)这样的边时才忽略不算。。。

但是其实只要有一个端点是0就好了啊。。。不管哪端是0,我就用这个0来完成工作。。。依然不增加重启次数。。。

这不是什么坑点。。。脑袋秀逗了。。。