poj 1325 Machine Schedule（最小顶点覆盖+最大匹配）

本文主要是介绍poj 1325 Machine Schedule（最小顶点覆盖+最大匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=1325

题意：有AB两台机器和k个任务，机器A有n种模式，机器B有m种模式，初始均工作在模式0，每个任务都可以由机器A的一种模式或机器B的一种模式完成，每次切换模式都需要代价1，要求用最小的代价完成所有任务。

思路：

A的n种模式和B的m种模式自成一个集合，显然是一个二分图的模型。令X= {机器A的模式}，Y={机器B的模式}， E= {（i,j）| job K 可由机器A的模式i或机器B的模式j完成}，这样构造了一个二分图G= {X,Y,E}.

本题是一类最小顶点覆盖的问题，将机器A和机器B的某个工作模式看做顶点，某个任务看做一条边，那么问题就转化为是否存在一个最小规模的点集，使得所有的边都至少和该点集中的一个顶点关联。

而二分图的最小顶点覆盖问题与最大匹

这篇关于poj 1325 Machine Schedule（最小顶点覆盖+最大匹配）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---