PKU 1325 - Machine Scheduling

本題源自北京賽區2002年的賽題。

假設有兩台機器a與b，分別有n和m個工作式模式。
現有K個工作，它可以分別在機器a和機器b兩種特定模式處理掉。
假設兩台機器都預設在0模式運作，問需要更改兩台機器次數總和最少使得工作能全部完成。

可以觀察到的是舉凡工作可以在其中一台機器的模式零運作都可以預先處理掉而不需更改兩台機器的運作模式。

剩下來的工作可以看成是二分圖的最小頂點覆蓋。根據konig's theorem，此問題等價於最大二分圖匹配。

難度系數從1.91804 降至1.91142。