算法分析

最小点覆盖：在给定的边中，每条边连着两个点，每条边至少选择1个点，最小能选多少个点

在二分图中，最大匹配数 == 最小点覆盖

题目描述到每台机器每次转换模式都需要启动一次，每个任务要么在A机器的a[i]模式进行，要么在B机器的b[i]模式进行，模式a[i]和模式b[i]连上一条边，即每条边至少选择1个模式(点)，最少能选多少个模式(点)，即求最小点覆盖问题

注意：两台机器一开始的模式是0，因此每个任务如果可以在模式为0的情况下进行，则不需要进行重启，可以舍去

时间复杂度 $O(nm)$

实际上远小于$O(nm)$

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110;
    static int n,m,k ;
    static boolean[] st = new boolean[N];
    static int[] match = new int[N];
    static boolean[][] g = new boolean[N][N];//连边

    static boolean find(int x)
    {
        for(int i = 0;i < m;i ++)
        {
            if(!st[i] && g[x][i])
            {
                st[i] = true;
                if(match[i] == 0 || find(match[i]))
                {
                    match[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(true)
        {
            n = scan.nextInt();
            if(n == 0) break;
            Arrays.fill(match, 0);
            for(int i = 0;i < n;i ++) Arrays.fill(g[i], false);
            m = scan.nextInt();
            k = scan.nextInt();
            while(k -- > 0)
            {
                int t = scan.nextInt();
                int a = scan.nextInt();
                int b = scan.nextInt();
                if(a == 0 || b == 0) continue; //若一开始的状态是0，则不需要重启
                g[a][b] = true;
            }

            int res = 0;
            for(int i = 1;i < n;i ++)
            {
                Arrays.fill(st, false);
                if(find(i)) res ++;
            }
            System.out.println(res);
        }

    }
}