3210996_ac_0ms_220k.c

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

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

int mid[256], fid[256];
char m[26][30], f[26][30];
char mm[27], ff[27];
int n;

int prefer(int i,char ch)
{
	int j;

	for(j = 2; j <= n+1; j++)
	{
		if(ch==f[i][j])
			return -j;
	}
	return 0;
}

void choose(int v)
{
	int i;

	for(i = 2; i <= n+1; i++)
	{
		if(ff[fid[m[v][i]]]==0)
		{
			ff[fid[m[v][i]]] = m[v][0];
			mm[v] = m[v][i];
			return ;
		}
		else
		{
			if(prefer(fid[m[v][i]],m[v][0])>prefer(fid[m[v][i]],ff[fid[m[v][i]]]))
			{
				int id = mid[ff[m[v][i]-'A']];
				ff[fid[m[v][i]]] = m[v][0];
				mm[v] = m[v][i];
				choose(id);
				return ;
			}
		}
	}
}

int main()
{
	int cas, i;
	char tmp[2];

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d",&n);
		for(i = 0; i < n; i++)
		{
			scanf("%s",tmp);
			mid[tmp[0]] = i;
		}
		for(i = 0; i < n; i++)
		{
			scanf("%s",tmp);
			fid[tmp[0]] = i;
		}
		for(i = 0; i < n; i++)
		{
			scanf("%s",m[i]);
		}
		for(i = 0; i < n; i++)
		{
			scanf("%s",f[i]);
		}
		memset(mm,0,sizeof(mm));
		memset(ff,0,sizeof(ff));
		for(i = 0; i < n; i++)
		{
			choose(i);
		}
		for(i = 0; i < n; i++)
		{
			printf("%c %c\n",m[i][0],mm[i]);
		}
		printf("\n");
	}
	return 0;
}