2196336_wa.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 58 行

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

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

bool init()
{
	int _x, _y, job;
    memset(g,0,sizeof(g));
    memset(link,0,sizeof(link));
    ans=0;
    scanf("%d",&n);
	if(!n)
		return false;
	scanf("%d%d",&m,&k);
    for(int i = 1; i <= k; i++)
    {
		scanf("%d%d%d",&job,&_x,&_y);
		if(_x*_y)
			g[_x][_y] = 1;
	}
	return true;
}

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()
{
	while(init())
	{
		for(int i = 1; i <= n; i++)
		{
			memset(b,0,sizeof(b));
			if(find(i))
				ans++;
		}
		printf("%d\n",ans);
	}
	return 1;
}