2196298_ac_30ms_312k.cpp

北大大牛代码 1240道题的原代码 超级权威

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

bool g[502][502];
int n,m,ans;
bool b[502];
int link[502];

void init()
{
	int _x, _y;
    memset(g,0,sizeof(g));
    memset(link,0,sizeof(link));
    ans=0;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++)
    {
		scanf("%d%d",&_x,&_y);
		g[_x][_y] = 1;
	}
}

bool find(int a)
{
	for(int i = 1; i<= n; i++)
	{
		if(g[a][ i ]==1&&!b[ i ])
		{
			b[ i ]=true;
            if(link[ i ]==0||find(link[ i ]))
			{
				link[ i ]=a;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	init();
	for(int i = 1; i <= n; i++)
	{
		memset(b,0,sizeof(b));
		if(find(i))
			ans++;
	}
	printf("%d\n",ans);
	return 1;
}