AcWing 376. 机器任务

题目传送门
本题 \(a[i]=0 || b[i]=0\)时可以跳过
一个任务\(i\)可以被\(A、B\)机器的两种状态\(a[i]、b[i]\)完成，将一个任务看成一条边，两种状态看成两个端点，
要完成一个任务就要从这两个点中选一个点(任务可以在\(A\)上执行也可以在\(B\)上执行)，
对于所有任务就要从\(N+M-2\)个点中(不包含初始\(0\)状态)选出最少的点，覆盖所有的边(任务)，
问题就变成求最小点覆盖问题(二分图中最小点覆盖等价于最大匹配数--匈牙利算法)。

#include 
using namespace std;

const int N = 110;

int n, m; // A机器n种模式,B机器m种模式
int k;    // k个任务
int match[N];
bool g[N][N], st[N];

bool find(int x) {
    for (int i = 0; i < m; i++) //枚举右部所有点
        if (!st[i] && g[x][i]) {
            st[i] = true;
            if (match[i] == -1 || find(match[i])) {
                match[i] = x;
                return true;
            }
        }
    return false;
}

int main() {
    while (cin >> n, n) {
        cin >> m >> k;
        memset(g, 0, sizeof g);          //邻接矩阵
        memset(match, -1, sizeof match); //因为本题中模式是0 ~ n-1，所以避开0,初始化-1
        //建图
        for (int i = 0; i < k; i++) {
            int t, a, b; //任务编号,在A机器中a模式执行，在B机器中b模式执行
            cin >> t >> a >> b;
            if (!a || !b) continue; //因为初始时就是0状态，不需要切换，如果是可以在状态0执行的，上来就整就可以了
            g[a][b] = true;         // ab之间连一条边，要么在a模式中执行，要么在b模式中执行，最小点覆盖
        }
        //最小点覆盖 等于  最大匹配数
        int res = 0;
        for (int i = 0; i < n; i++) { //枚举左部每个点
            memset(st, 0, sizeof st);
            if (find(i)) res++;
        }
        //输出
        cout << res << endl;
    }
    return 0;
}