解题思路

1. 初始化函数 init：
   • 清空邻接表 lnklst，并调整其大小为 n1 + 1。
   • 清空左部点的匹配数组 l，并调整其大小为 n1 + 1，初始值为 -1。
   • 清空右部点的匹配数组 r，并调整其大小为 n2 + 1，初始值为 -1。
2. 添加边函数 add_edge：
   • 将顶点 v 添加到顶点 u 的邻接表 lnklst[u] 中，表示存在从 u 到 v 的边。
3. 深度优先搜索函数 dfs：
   • 对于顶点 u 的邻接表中的每个顶点 v：
     • 如果 v 已被访问，则跳过。
     • 标记 v 为已访问。
     • 如果 v 未匹配，或者 v 的匹配点可以找到其他匹配（递归调用 dfs(r[v])），则更新匹配关系 l[u] = v 和 r[v] = u，并返回 true。
     • 如果无法找到匹配，则返回 false。
4. 贪心匹配函数 greedy_match：
   • 遍历左部点 u：
     • 如果 u 未匹配，则遍历 u 的邻接表。
     • 如果邻接表中的顶点 v 未匹配，则进行匹配 l[u] = v 和 r[v] = u，匹配数 match 加 1，并跳出循环。
   • 返回贪心匹配的数量 match。
5. 匈牙利算法函数 hungarian：
   • 先调用 greedy_match 进行贪心匹配，得到初始匹配数 match。
   • 遍历左部点 u：
     • 如果 u 未匹配，则初始化访问数组 visited。
     • 调用 dfs(u)，如果能找到增广路径（即匹配数增加），则匹配数 match 加 1。
   • 返回最终的最大匹配数 match。
6. 主函数 main：
   • 持续读取输入的二分图信息，包括左部点数量 n、右部点数量 m 和边的数量 k。
   • 调用 init 进行初始化。
   • 读取每条边的信息 x 和 y，调用 add_edge 添加边。
   • 调用 hungarian 计算最大匹配数，并输出结果。

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > lnklst;
vector<int> l, r;
vector<bool> visited;

/* make all vectors one element bigger in case the index starts from 1 instead of 0 */
void init(int n1, int n2) {
	lnklst.clear(); lnklst.resize(n1+1);
	l.clear(); l.resize(n1+1,-1);
	r.clear(); r.resize(n2+1,-1);
	return;
}

void add_edge(int u, int v) {
	lnklst[u].push_back(v);
	return;
}

bool dfs(int u) {
	for (int i=0; i<lnklst[u].size(); i++) {
		int v = lnklst[u][i];
		if (visited[v]) continue;
		visited[v] = true;
		if (r[v] < 0 || dfs(r[v])) {
			l[u] = v;
			r[v] = u;
			return true;
		}
	}
	return false;
}

int greedy_match(int n1) {
	int match = 0;
	for (int u=0; u<n1; u++) {
		if (l[u] < 0) {
			for (int i=0; i<lnklst[u].size(); i++) {
				int v = lnklst[u][i];
				if (r[v] < 0) {
					l[u] = v;
					r[v] = u;
					match++;
					break;
				}
			}
		}
	}
	return match;
}

int hungarian(void) {
	int n1 = l.size();
	int n2 = r.size();
	int match = greedy_match(n1);
	for (int u=0; u<n1; u++) {
		if (l[u] < 0) {
			visited.clear();
			visited.resize(n2);
			if (dfs(u)) {
				match++;
			}
		}
	}
	return match;
}

int main() {
	int n, m, k, i, j, x, y;
	while (true)
	{
		scanf("%d", &n);
		if (n == 0) break;
		scanf("%d %d", &m, &k);
		init(n, m);
		for (j = 0; j < k; j++)
		{
			scanf("%d %d %d", &i, &x, &y);
			if (x != 0 && y != 0) add_edge(x+1, y+1);
		}
		printf("%d\n", hungarian());
	}

	return 0;
}