2534271_ac_139ms_624k.cpp

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

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

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

void insert(int k)
{
	int i;

	for(i = 0; menu[k][i] != '\0'; i++)
			map[l][menu[k][i]-'A'] = 1;
}

int dfs(int v)
{
	int i;

	for(i = 0; i < 26; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(link[i]==-1||dfs(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(!dfs(i))
			return 0;
	}
	return 1;
}

int main()
{
	int i, k, j;
	char tmp;

	n = 0;
	while(1)
	{
		i = 0;
		while(1)
		{
			if((tmp = getchar())==EOF)
				goto bre;
			if(tmp=='\n')
			{
				menu[n][i] = '\0';
				break;
			}
			if(tmp=='>'||tmp=='<')
			{
				getchar();
				menu[n][0] = tmp;
				break;
			}
			if(tmp<='Z'&&tmp>='A')
				menu[n][i++] = tmp;
		}
		n++;
	}
bre:
	memset(mark,-1,sizeof(mark));
	for(i = 0; i < n; i++)
	{
		if(menu[i][0]=='>')
		{
			memset(map,0,sizeof(map));
			l = 0;
			for(j = i-1; j >= 0; j--)
			{
				if(mark[j] != -1)
					j = mark[j];
				else
				{
					if(menu[j][0]=='<')
						break;
					else
						insert(j),l++;
				}
			}
			for(k = j; k <= i; k++)
				mark[k] = j;
			if(l>26)
			{
				printf("No Solution\n");
				return 1;
			}
			if(j)
			{
				int tt;
				tt = 1;
				for(k = 0; menu[j-1][k]!='\0'; k++)
				{
					map[l][menu[j-1][k]-'A'] = 1;
					l++;
					if(!match())
					{
						map[--l][menu[j-1][k]-'A'] = 0;
						strcpy(&menu[j-1][k],&menu[j-1][k+1]);
						k--;
						continue;
					}
					else
						tt = 0;
					l--;
					map[l][menu[j-1][k]-'A'] = 0;
				}
				if(tt)
				{
					printf("No Solution\n");
					return 1;
				}
			}
			else
				if(!match())
				{
					printf("No Solution\n");
					return 1;
				}
				else
				{
					printf("Got It!\n");
					return 1;
				}
		}
	}
	return 1;
}