学步园

这道题目,还是应该看成是定理题目,自己也不能够证明够出为什么给要这么做.....

有空一定要去问问别人,当然我也会自己找课件看看的...

很好敲,,

留下代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int N,M;
int map[125][125];
int visit[125];
int link[125];

int getnum(int x)
{
	for(int i=1;i<=N;i++)
	{
		if(!visit[i]&&map[x][i])
		{
			visit[i]=1;
			if(!link[i]||getnum(link[i]))
			{
				link[i]=x;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(map,0,sizeof(map));
		int count=0;
		memset(link,0,sizeof(link));
		scanf("%d%d",&N,&M);
		int a,b;
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d",&a,&b);
			map[a][b]=1;
		}
		for(i=1;i<=N;i++)
		{
			memset(visit,0,sizeof(visit)); 
			if(getnum(i))
				count++;
		}
		printf("%d\n",N-count);
	}
	return 0;
}