pku1325.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define SIZE 110

int st[SIZE][SIZE];
int match[SIZE];
int chk[SIZE], chA[SIZE], chB[SIZE];
int total;
int A, B, K;

int InsA(int x)
{
	if (chA[x])
	{
		return 0;
	}
	chA[x] = 1;
	return 1;
}

int InsB(int x)
{
	if (chB[x])
	{
		return 0;
	}
	chB[x] = 1;
	return 1;
}

int DFS(int p)
{
	int i, t;
	for (i = 0; i < A; i++)
	{
		if (st[i][p] && !chk[i])
		{
			chk[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[i] = t;
		}
	}
	return 0;
}

int Solve()
{
	int i, id, s, e, cnt, ans;
	memset(chA, 0, sizeof(chA));
	memset(chB, 0, sizeof(chB));
	memset(st, 0, sizeof(st));
	memset(match, -1, sizeof(match));
	cnt = 0;
	while (K--)
	{
		scanf("%d %d %d", &id, &s, &e);
		if (!(s * e))
		{
			continue;
		}
		cnt += InsA(s);
		cnt += InsB(e);
		st[s][e] = 1;
	}
	for (i = 0, ans = 0; i < B; i++)
	{
		memset(chk, 0, sizeof(chk));
		ans += DFS(i);
	}
	printf("%d\n", ans);
}

int main()
{
	while (scanf("%d %d %d", &A, &B, &K) == 3)
	{
		Solve();
	}
	return 0;
}