该题是经典的二分图匹配的应用，题义是这样的。给定K个工作，有两台机器，A机器有N种工作状态，B机器有M种工作状态，对于每一个工作，既可以被A完成又可以被B完成，求完成所有工作至少需要转换多少次模式。

将A以及B的不同模式作为二分图的两个部分，工作作为边，则该题转化为求解最小顶点覆盖来求解。

最小顶点覆盖：包含二分图的X，Y部的部分顶点的一个集合，使得所有的边至少有一个顶点在该点集内。最小顶点覆盖就等于二分图的最大匹配。

证明如下：

设二分图的最大匹配数为M（下图中M等于2），现假设下面的二分图只有 （A，a）以及（C，c）两条边，我们通过增加边来还原至原本的图。这个增加边的过程是不能够使得二分图的匹配数增加的。我们在（A，a）以及（C，c）中选取两点作为最小覆盖点（注意定义，只能这样选），我们选取A，C。现在我们来推翻我们的假设，我们就要增加一些边，使得没有端点在A，C里面（注意不能增加匹配数），刚开始想很简单对吧，我们添加一条边（D，c），呵呵完成了，没有在A，C中，不过这并不能推翻我们的结论，因为A，C是我随机选取的两个点，我可以改变主意了，选择A，c作为最小覆盖点。（B，d）行吗？不行，这样匹配数会增加1了，（A，b），（B，c）和（C，d）行吗？看起是没有增加匹配数，由于A点必须选，C，c也都必须选啊，几轮错了吗？ 不需要注意我们也已经增加了匹配数，有了增广路径了。不信，你可以用程序跑一跑。由此特殊性的列子我们得出这个结论应该是靠谱的。（不会严谨的证明，>.<!!!）

A　-----　a

B　      　b

C　-----　c

D　　　　d

得出了结论，代码出来了，注意在0状态是不用统计转换次数的，因为机器本身停留在mode_0

代码如下：

#include 
     
       #include 
      
        #include 
       
         using namespace std; int N, M, K, visit[105], marry[105]; int G[105][105]; int path(int u) {
   for (int i = 0; i < M; ++i) {
   if (!G[u][i] || visit[i]) continue;         visit[i] = 1; if (marry[i] == -1 || path(marry[i])) {
               marry[i] = u; return 1;         }     } return 0; } int main() {
   int a, x, y, ans; while (scanf("%d", &N), N) {
           scanf("%d %d", &M, &K);         ans = 0;         memset(G, 0, sizeof (G));         memset(marry, 0xff, sizeof (marry)); for (int i = 0; i < K; ++i) {
               scanf("%d %d %d", &a, &x, &y);             G[x][y] = 1;         } for (int i = 0; i < N; ++i) {
               memset(visit, 0, sizeof (visit)); if (path(i)) {
                   ++ans;             }         } for (int i = 0; i < M; ++i) {
   if (marry[i] == 0 && i != 0) {
                   --ans; break;             }         } if (marry[0] != -1)             --ans;         printf("%d\n", ans);     } return 0; }