4233426_ac_157ms_660k.cc

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

#include<iostream>
int pperson,nxx,nyy,nx,ny,m,nbs[501],next[62500],ev[62500],num,cx[501],cy[501],*ne,*e,*c,*y,*n;
bool sy[501],s;
int path(int u)
{ 
	int i=nbs[u],v;
	for(;i;i=next[i])
	{
		v=ev[i];
		if(false==sy[v])
		{
			sy[v]=true;
			if(cy[v]==0||path(cy[v]))
			{
				cx[u]=v;
				cy[v]=u;
				return true;
			}
		}
	}
	return false;
}
int MaximumMatch()
{ 
	int i,ret=0;
	memset(cx,0,4*nxx);
	memset(cy,0,4*nyy);
	for(i=1;i<=nx;i++)
		if(cx[i]==0)
		{
			memset(sy,0,nyy);
			if(path(i))ret++;
		} else while(1);
	return ret;
}
int h1[501],h2[501];
char music1[501][20],music2[501][20],sport1[501][20],sport2[501][20];
int aabs(int n)
{
	return n<0?-n:n;
}
int main()
{
	int cs,t,person,i,j;
	char tp[20];
	scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&person);
		pperson=person+1;
		nx=ny=0;
		while(person--)
		{
			scanf("%d%s",&t,tp);
			if(tp[0]=='M')
			{
				h1[++nx]=t;
				scanf("%s%s",music1[nx],sport1[nx]);
			}
			else
			{
				h2[++ny]=t;
				scanf("%s%s",music2[ny],sport2[ny]);
			}
		}
		nyy=ny+1;
		nxx=nx+1;
		memset(nbs,0,nxx*4);
		num=0;
		for(i=1;i<=nx;i++)
			for(j=1;j<=ny;j++)
				if(aabs(h1[i]-h2[j])<=40&&strcmp(music1[i],music2[j])==0&&strcmp(sport1[i],sport2[j]))
				{
					next[++num]=nbs[i];
					ev[nbs[i]=num]=j;
				}
		printf("%d\n",nx+ny-MaximumMatch());
	}
	return 0;
}