2533341_wa.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 97 行

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

char menu[10001][51];
int mark[10001];
int flag[27];
int map[27][27], link[27], b[27];
int l, r;

void insert_edge(int k)
{
	int i;

	for(i = 0; menu[k][i]!='\0'; i++)
	{
		if(menu[k][i]<='Z'&&menu[k][i]>='A'&&(i==0||menu[k][i-1]==' '))
		{
			if(flag[menu[k][i]-'A']==-1)
			{
				flag[menu[k][i]-'A'] = r;
				map[l][r++] = 1;
			}
			else
				map[l][flag[menu[k][i]-'A']] = 1;
		}
	}
}

int find(int v)
{
	int i;

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

int match()
{
	int i;

	memset(link,-1,sizeof(link));
	for(i = 0; i < l; i++)
	{
		memset(b,0,sizeof(b));
		if(!find(i))
			return 0;
	}
	return 1;
}

int main()
{
	int i = 0, j, k;

	while(gets(menu[i])!=NULL)
		i++;
	for(j = 0; j < i; j++)
	{
		if(menu[j][0]=='>')
		{
			memset(flag,-1,sizeof(flag));
			l = r = 0;
			mark[j] = 1;
			for(k = j-1; k >= 0; k--)
			{
				if(!mark[k])
				{
					mark[k] = 1;
					if(menu[k][0]=='<')
						break;
					insert_edge(k);
					l++;
				}
			}
			if(k)
				insert_edge(k-1),l++;
			if(l>r||!match())
			{
				printf("No Solution\n");
				return 1;
			}
		}
	}
	printf("Got It!\n");
	return 1;
}