学步园

最大匹配裸题

两题题目都一样，第一个人的牌已经放好，问第二个人怎么放自己的牌赢得最多，

如果同一列的牌比对方大，就赢一次

将第二个人的每张牌与第一个人比较，如果大于第一个人的牌，两张牌就可以建一条边，

然后就是求最大匹配了

#include<stdio.h>
#include<string.h>
#define N 60
int n,map[N][N],x[N],y[N],match[N],vis[N];
int find(int x)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(vis[i]==0&&map[x][i]==1)
		{
			vis[i]=1;
			if(match[i]==-1||find(match[i])==1)
			{
				match[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
    int i,j,k,t,sum;
	char str[3];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(j=1;j<=2;j++)
		{
			for(i=1;i<=n;i++)
			{
				scanf("%s",str);
				if(str[0]>='2'&&str[0]<='9')
				{
					k=(str[0]-'2')*4;
				}
				else
				{
					if(str[0]=='T')
						k=8*4;
					else if(str[0]=='J')
						k=9*4;
					else if(str[0]=='Q')
						k=10*4;
					else if(str[0]=='K')
						k=11*4;
					else if(str[0]=='A')
						k=12*4;
				}
				if(str[1]=='C')
					k+=1;
				else if(str[1]=='D')
					k+=2;
				else if(str[1]=='S')
					k+=3;
				else if(str[1]=='H')
					k+=4;
				if(j==1)
					x[i]=k;
				else y[i]=k;
			}
		}
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(y[i]>x[j])
					map[i][j]=1;
			}
			memset(match,-1,sizeof(match));
			sum=0;
			for(i=1;i<=n;i++)
			{
				memset(vis,0,sizeof(vis));
				sum+=find(i);
			}
			printf("%d\n",sum);
	}
	return 0;
}