2327075_ac_0ms_56k.c

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

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

int b[6], link[6][21];
int map[21][6];
int cap[6];

int mark(char ch)
{
	switch(ch)
	{
	case 'S':return 1;
	case 'M':return 2;
	case 'L':return 3;
	case 'X':return 4;
	case 'T':return 5;
	}
	return 0;
}

int find(int v)
{
	int i, j;

	for(i = 1; i <= 5; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(cap[i])
			{
				cap[i]--;
				link[i][++link[i][0]] = v;
				return 1;
			}
			else
			{
				for(j = 1; j <= link[i][0]; j++)
					if(find(link[i][j]))
					{
						link[i][j] = v;
						return 1;
					}
			}
		}
	}
	return 0;
}

int input()
{
	int i, j, x;
	char tmp[6];

	scanf("%s",tmp);
	if(tmp[0]=='E')
		return 0;
	scanf("%d",&x);
	memset(map,0,sizeof(map));
	for(i = 1; i <= x; i++)
	{
		scanf("%s",tmp);
		for(j = mark(tmp[0]); j <= mark(tmp[1]); j++)
			map[i][j] = 1;
	}
	for(i = 1; i <= 5; i++)
		scanf("%d",&cap[i]);
	memset(link,0,sizeof(link));
	for(i = 1; i <= x; i++)
	{
		memset(b,0,sizeof(b));
		if(!find(i))
		{
			printf("I'd rather not wear a shirt anyway...\n");
			goto ret;
		}
	}
	printf("T-shirts rock!\n");
ret:
	scanf("%s",tmp);
	return 1;
}

int main()
{
	while(input());
	return 1;
}