分析
起初,机器 $A, B$ 都处于 $0$ 模式,可以把所有 $0$ 模式任务处理掉,无需重启机器。对于剩余任务,此时 $a_i, b_i > 0$,最多需要 $n + m - 2$ 种模式
把剩余模式抽象为点,任务 $i$ 抽象为一条从 $a_i$ 到 $b_i$ 的无向边,问题等价于至少选几个点,能覆盖所有边,即最小点覆盖。显然,该图是一个二分图,因此最小点覆盖等于最大匹配数
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110;
int n, m, k;
int match[N];
bool g[N][N], st[N];
bool find(int x) {
for (int i = 1; i <= m; i ++)
if (!st[i] && g[x][i]) {
st[i] = 1;
int& bf = match[i];
if (!bf || find(bf))
return bf = x;
}
return 0;
}
int main() {
while (cin >> n, n) {
cin >> m >> k;
memset(g, 0, sizeof g);
memset(match, 0, sizeof match);
for (int t, a, b; k; k --) {
cin >> t >> a >> b;
if (a && b) g[a][b] = 1;
}
int ans = 0;
for (int i = 1; i <= n; i ++) {
memset(st, 0, sizeof st);
if (find(i)) ans ++;
}
cout << ans << endl;
}
return 0;
}