pku1422.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 62 行

#include <stdio.h>
#include <string.h>
#define SIZE 210
int N, M;
int st[SIZE][SIZE];
int match[SIZE], chk[SIZE];

int DFS(int p)
{
	int i, t;
	for (i = 1; i <= N; i++)
	{
		if (p == i)
		{
			continue;
		}
		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;
}

void Solve()
{
	int i, s, e;
	int res;
	memset(st, 0, sizeof(st));
	memset(match, -1, sizeof(match));
	for (i = 0; i < M; i++)
	{
		scanf("%d %d", &s, &e);
		st[s][e] = 1;
	}
	for (i = 1, res = 0; i <= N; i++)
	{
		memset(chk, 0, sizeof(chk));
		res += DFS(i);
	}
	printf("%d\n", N - res);
}

int main()
{
	int T_T;
	scanf("%d", &T_T);
	while (T_T-- && scanf("%d %d", &N, &M) != -1)
	{
		Solve();
	}
	return 0;
}