• 这个概念针对任意的无向图都是成立的。是指我们从图中选出最少的点集，使得所有的边中的两个端点至少有一个端点在该点集中。

• 在二分图中，最小点覆盖n==最大匹配数m。假设在二分图中最小点覆盖为n，最大匹配数为m，下面证明$n \ge m$且等号可以成立。

（1）首先证明$n \ge m$。因为对于最大匹配来说，每两条边之间没有公共点，要想把所有用点覆盖所有的边，则必须每条边都选一个端点，所以$n \ge m$。

（2）证明等号可以成立。这里使用构造性证明。

​ （2.1）求二分图的最大匹配；

​ （2.2）从左部每个非匹配点出发，做一遍增广（一定不会成功，成功的话就可以换成增广了），标记所有经过的点（左右都需要标记）

做完上面的步骤之后，就可以构造出一个最小覆盖的方案，方案中包含的点=左部所有未被标记的点+右部所有被标记的点。如下图：

因为：方案中包含的点 = 左部所有未被标记的点 + 右部所有被标记的点。又左部所有未被标记的点一定是匹配点（逆否命题），右部所有被标记的点一定是匹配点（逆否命题），因为又有性质③，对于每条匹配边，我们必然只选其中的一个点，被标记的选择右边的点，未被标记的选择左边的点，所以n可以取到m。

根据在左部右部，以及匹配不匹配的情况，我们可以构造出四种边：

① 左边匹配，右边匹配；②左边非匹配，右边匹配；③ 左边匹配，右边非匹配；④ 左边非匹配，右边非匹配；

对于第①种情况我们已经讨论过；对于第④种情况不可能出现，否则的话我们求的不是最大匹配。

对于第②种情况，左边非匹配的点一定是被标记的点，因为走的是增广路径，走到右部的点一定是被标记的，这样的边一定被选；

对于第③种情况，这种情况不可能存在，右边非匹配一定没有被标记，因此左部的点不可能是匹配点；

• 综上所述，我们证明了$n \ge m$且可以取到m，将所有的边覆盖住，因此$n == m$。

分析

• 一个任务可以在A、B两台机器中的任意一个被完成。刚开始A、B都处于模式0，因此需要切换到0的任务不需要重启就可以完成，可以不用考虑（因为不会影响重启次数）。

• 我们的问题可以转换成：需要从A、B的N+M-2个模式当中最少选择多少个模式可以把每个任务完成，如果将$a[i]、b[i]$之间连一条无向边，则把每个任务完成相当于在这条无向边上选择一个点。因此为题最终变为了：我们最少需要选择多少点可以把所有的边全部覆盖住。这是一个最小点覆盖的问题。

• 又因为这是一个二分图，所以最小点覆盖n==最大匹配数m，我们求一遍最大匹配即可。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m, k;
bool g[N][N];  // 表示两点之间是否有任务
int match[N];
bool st[N];

bool find(int x) {

    for (int i = 1; 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);

        while (k--) {
            int t, a, b;
            cin >> t >> a >> b;
            if (!a || !b) continue;
            g[a][b] = true;  // 只需要记录从第一个集合到第二个集合的边即可
        }

        int res = 0;
        for (int i = 1; i < n; i++) {
            memset(st, 0, sizeof st);
            if (find(i)) res++;
        }

        cout << res << endl;
    }

    return 0;
}