2850083_ac_0ms_100k.c

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

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

int n;
int map[27][27];
int b[27], link[27];
char adam[27][3], eva[27][3];
char poker[] = "23456789TJQKA";
char color[] = "CDSH";
int f(char a)
{
	return strchr(poker,a)-poker;
}

int g(char a)
{
	return strchr(color,a)-color;
}

int bigger(int a,int b)
{
	if(eva[a][0]!=adam[b][0])
		return f(eva[a][0])>f(adam[b][0]);
	else
		return g(eva[a][1])>g(adam[b][1]);
}

int dfs(int v)
{
	int i;

	for(i = 1; i <= n; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(link[i]==0||dfs(link[i]))
			{
				link[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int cas, i, j, ans;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d",&n);
		for(i = 1; i <= n; i++)
			scanf("%s",adam[i]);
		for(i = 1; i <= n; i++)
			scanf("%s",eva[i]);
		memset(map,0,sizeof(map));
		for(i = 1; i <= n; i++)
			for(j = 1; j <= n; j++)
				if(bigger(i,j))
					map[i][j] = 1;
		ans = 0;
		memset(link,0,sizeof(link));
		for(i = 1; i <= n; i++)
		{
			memset(b,0,sizeof(b));
			ans += dfs(i);
		}
		printf("%d\n",ans);
	}
	return 0;
}