记录编号	42314	评测结果	AAAATAAA
题目名称	1072.[ZSTU 2579] 著名医生的药方	最终得分	87
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	15.804 s
提交时间	2012-09-18 22:15:12	内存使用	3.18 MiB

#include <cstdio>
#include <cstring>
using namespace std;

struct record
{
	int data[510],rest;
	bool una[510];
};

int n,p,waynum[510],way[510][510],outnum/*,outp[60000][510]*/;
bool map[510][510];

void swap(int& x,int& y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

bool check(record now)
{
	int i;
	for (i=1;i<p;i++)
		if (now.data[i]&&now.data[i+1]&&!map[now.data[i]][now.data[i+1]])
			return(false);
	return(true);
}

record change(record now,int deep,int pos)
{
	int i,bef;
	bef=now.data[deep-1];
	now.data[deep]=pos;
	if (now.una[pos]==false)
		now.rest--;
	now.una[pos]=true;
	if (bef)
		for (i=0;i<waynum[bef];i++)
		{
			if (now.una[way[bef][i]]==false)
				now.rest--;
			now.una[way[bef][i]]=true;
		}
	return(now);
}

void dfs(record now,int deep)
{
	int i;
	if (deep>p)
	{
//		for (i=1;i<=p;i++)
//			outp[outnum][i]=now.data[i];
		outnum++;
		return;
	}
	if (now.rest<=p-deep)
		return;//short cut
	int temp,bef;
	temp=now.data[deep];
	bef=now.data[deep-1];
	if (temp)
	{
		if (now.una[temp]||!map[bef][temp])
			return;
		else
		{
			if (bef)
				for (i=0;i<waynum[bef];i++)
				{
					if (now.una[way[bef][i]]==false)
						now.rest--;
					now.una[way[bef][i]]=true;
				}
			dfs(now,deep+1);
			return;
		}
	}
	int aft;
	aft=now.data[deep+1];
	for (i=0;i<waynum[bef];i++)
	{
		if (!now.una[way[bef][i]]&&map[way[bef][i]][aft])
		{
			dfs(change(now,deep,way[bef][i]),deep+1);
		}
	}
}

void dfs2(record now,int deep)
{
	int i;
	if (deep>p)
	{
		for (i=1;i<p;i++)
			printf("%d ",now.data[i]);
		printf("%d\n",now.data[p]);
//		outnum++;
		return;
	}
	if (now.rest<=p-deep)
		return;//short cut
	int temp,bef;
	temp=now.data[deep];
	bef=now.data[deep-1];
	if (temp)
	{
		if (now.una[temp]||!map[bef][temp])
			return;
		else
		{
			if (bef)
				for (i=0;i<waynum[bef];i++)
				{
					if (now.una[way[bef][i]]==false)
						now.rest--;
					now.una[way[bef][i]]=true;
				}
			dfs2(now,deep+1);
			return;
		}
	}
	int aft;
	aft=now.data[deep+1];
	for (i=0;i<waynum[bef];i++)
	{
		if (!now.una[way[bef][i]]&&map[way[bef][i]][aft])
		{
			dfs2(change(now,deep,way[bef][i]),deep+1);
		}
	}
}

int main(void)
{
	freopen("doctor.in","r",stdin);
	freopen("doctor.out","w",stdout);
	char str[2000];
	int iex,i,j,k,len,num;
	record rec={0};
	scanf("%d\n",&n);
	for (i=0;i<n;i++)
	{
		way[0][i]=i+1;
		map[0][i+1]=true;
		map[i+1][0]=true;
	}
	waynum[0]=n;
	for (iex=1;iex<=n;iex++)
	{
		scanf("%[^\n]\n",&str);
		while (str[0]<'0'||str[0]>'9')
			scanf("%[^\n]\n",&str);
		len=strlen(str);
		for (i=0;i<len;i++)
		{
			if (str[i]>='0'&&str[i]<='9')
			{
				j=i;
				while (str[j]>='0'&&str[j]<='9')
					j++;
				j--;
				num=0;
				for (k=i;k<=j;k++)
					num=num*10+str[k]-'0';
				way[iex][waynum[iex]++]=num;
				map[iex][num]=true;
				i=j;
			}
		}
		for (i=0;i<=waynum[iex]-2;i++)
			for (j=0;j<=waynum[iex]-i-2;j++)
				if (way[iex][j]>way[iex][j+1])
					swap(way[iex][j],way[iex][j+1]);
	}
	scanf("%d",&p);
	for (i=1;i<=p;i++)
		scanf("%d",&rec.data[i]);
	if (!check(rec))
	{
		printf("0\n");
		return(0);
	}
	rec.rest=n;
	dfs(rec,1);
	printf("%d\n",outnum);
//	for (i=0;i<outnum;i++)
//	{
//		for (j=1;j<p;j++)
//			printf("%d ",outp[i][j]);
//		printf("%d\n",outp[i][p]);
//	}
	dfs2(rec,1);
	return(0);
}