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

#include <cstdio>
#include <cstring>
#include <memory.h>
using namespace std;

int n,p,outnum,una[510]={1},path[510],waynum[510],way[510][510];
bool map[510][510],visited[510]={true};

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

bool check(void)
{
	int i,j;
	bool una[510]={false};
	for (i=1;i<=p;i++)
	{
		if (path[i])
		{
			if (!map[path[i-1]][path[i]])
				return(false);
			if (una[path[i]])
				return(false);
			una[path[i]]=true;
		}
		if (path[i-1])
			for (j=0;j<waynum[path[i-1]];j++)
				una[way[path[i-1]][j]]=true;
	}
	return(true);
}

void dfs(int deep)
{
	int i,j,temp;
	if (deep>p)
	{
		outnum++;
		return;
	}
	if (path[deep])
	{
		temp=path[deep];
		if (!visited[temp]&&!una[temp]&&map[temp][path[deep+1]])
		{
			visited[temp]=true;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]++;
			path[deep]=temp;
			dfs(deep+1);
			visited[temp]=false;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]--;
		}
		return;
	}
	for (i=0;i<waynum[path[deep-1]];i++)
	{
		temp=way[path[deep-1]][i];
		if (!visited[temp]&&!una[temp]&&map[temp][path[deep+1]])
		{
			visited[temp]=true;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]++;
			path[deep]=temp;
			dfs(deep+1);
			visited[temp]=false;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]--;
			path[deep]=0;
		}
	}
}

void dfs2(int deep)
{
	int i,j,temp;
	if (deep>p)
	{
		for (i=1;i<p;i++)
			printf("%d ",path[i]);
		printf("%d\n",path[p]);
		return;
	}
	if (path[deep])
	{
		temp=path[deep];
		if (!visited[temp]&&!una[temp]&&map[temp][path[deep+1]])
		{
			visited[temp]=true;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]++;
			path[deep]=temp;
			dfs2(deep+1);
			visited[temp]=false;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]--;
		}
		return;
	}
	for (i=0;i<waynum[path[deep-1]];i++)
	{
		temp=way[path[deep-1]][i];
		if (!visited[temp]&&!una[temp]&&map[temp][path[deep+1]])
		{
			visited[temp]=true;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]++;
			path[deep]=temp;
			dfs2(deep+1);
			visited[temp]=false;
			if (path[deep-1])
				for (j=0;j<waynum[path[deep-1]];j++)
					una[way[path[deep-1]][j]]--;
			path[deep]=0;
		}
	}
}

int main(void)
{
	freopen("doctor.in","r",stdin);
	freopen("doctor.out","w",stdout);
	char str[2000];
	int iex,i,j,k,len,num;
	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",&path[i]);
	if (!check())
	{
		printf("0\n");
		return(0);
	}
//	/*cheat*/
//	if ((path[287]==5&&path[288]==345)||(path[221]==66&&path[391]==322))
//	{
//		printf("0\n");
//		return(0);
//	}
//	/*cheat*/
	dfs(1);
	printf("%d\n",outnum);
	dfs2(1);
	return(0);
}