POJ 1325 Machine Schedule

题意

给你两台机器和k个工件，要你设计最优调度方案。对于每个机器，一共有0 ~ n-1(或者是m-1)这n(或者是m)个状态，初始状态都是0。对于每个工件，要么在x号状态下加工，要么在y号状态下加工。你要给出两台机器一共最少要切换多少次状态，才可以加工完全部工件。

思路

这个题对于建图是很讲究的，第一眼看上去很有二分图的意思。但是如果你这么建图：一边是0~max(m,n)这些状态(因为无论是两台还是一台，其实都是一样的，因为机器运转的时间是无限的，理论上讲就算只给一个机器，也能完成任务，而且和两台机器所需要的切换次数一样)，另一边是0~k这些工件，每一个工件都和他可以被加工的状态连上一条边。

但是这么建图并不能解决问题，首先，只要工件可以在0状态加工，就可以看成不存在了，因为机器无需切换状态就可以加工好，这样，我们在图中所有与0状态相连的点，和0状态本身都要去掉。其次，现在我们规约好的问题已经变成了：在一边的图中选出尽可能少的点，使得这些点的所连接的点可以覆盖对面全部的点。这是典型的“最小支配集”问题。最小支配集问题目前还是NP困难问题。所以此路已经不通了。

我们只好换一种思路，我们发现，如果把一个工件可以加工的两个状态连接起来，建立二分图之后。在这个图上，图的两边分别是A机器和B机器，图上的每一条边代表一个工件，我们要求的东西就变成了选出最少的点，使得所引出的边的集合中包含了全部的边，也就是“最小点覆盖问题”。二分图的最大匹配数等于最小覆盖数。问题可做了。

代码

使用了匈牙利算法。