记录编号	42783	评测结果	AATATTWA
题目名称	[ZSTU 2579] 著名医生的药方	最终得分	50
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	3.999 s
提交时间	2012-09-29 14:46:27	内存使用	3.70 MiB

#include <fstream>
using namespace std;
ifstream cin("doctor.in");
ofstream cout("doctor.out");
int n,p,a[501][501],yao[1001],ans=0,b[501],c[501],ct[501];
string st;
void init()
{
	int k=0,i;
	cin>>n;getline(cin,st);
	for (i=1;i<=n;i++)
	{
		while (cin.peek()!=10&&cin.peek()!=13) cin>>a[i][++k];
		getline(cin,st);c[i]=k;k=0;
	}
	cin>>p;
	for (i=1;i<=n;i++) {b[i]=0;ct[i]=-1;}
	for (i=1;i<=p;i++) 
	{
		cin>>yao[i];
		if (yao[i]!=0) 
		{
			b[yao[i]]=1;
			ct[yao[i]]=i;
		}
	}
}
bool keyi(int r,int x,int y)//判断r--x,y--r是否可行
{
	int i,j=1;
	if (b[r]!=0) return false;//r是否用过
	for (i=1;i<=c[y];i++)//r是否是y的后继
		if (r==a[y][i]) j=0;
	if (j==1) return false;
	j=1;//x是否是r的后继
	if (x!=0)
	{
		for (i=1;i<=c[r];i++)
			if (x==a[r][i]) j=0;
		if (j==1) return false;
	}
	return true;
}
bool keyi1(int r,int x,int y)//判断r--x,y--r是否可行
{
	int i,j=1;
	
	for (i=1;i<=c[y];i++)//r是否是y的后继
		if (r==a[y][i]) j=0;
	if (j==1) return false;
	j=1;//x是否是r的后继
	if (x!=0)
	{
		for (i=1;i<=c[r];i++)
			if (x==a[r][i]) j=0;
		if (j==1) return false;
	}
	return true;
}
bool hh(int step,int x)
{
	for (int i=1;i<=c[yao[step-1]];i++)
		if (ct[a[yao[step-1]][i]]>step) return 0;
	return 1;
}
void jia(int x)
{
	int i;
	for (i=1;i<=c[x];i++) b[a[x][i]]++;
	b[x]++;
}
void jian(int x)
{
	int i;
	for (i=1;i<=c[x];i++) b[a[x][i]]--;b[x]--;
}
void pd()
{
	for (int i=1;i<p;i++) cout<<yao[i]<<' ';
	cout<<yao[p]<<endl;
}
void dfs(int step)
{
	int r;
	if (step>p) ans++;else
	{
		if (yao[step]==0)
		{
			for (r=1;r<=n;r++)
			{
				if (step==1)
				{
					yao[1]=r;b[r]++;
					dfs(step+1);
					yao[1]=0;b[r]--;
				}else
				{
					if (keyi(r,yao[step+1],yao[step-1])&&hh(step,r))
					{
						jia(yao[step-1]);yao[step]=r;
						dfs(step+1);
						jian(yao[step-1]);yao[step]=0;
					}
				}
			}
		}else 
			if (keyi1(yao[step],yao[step+1],yao[step-1])&&hh(step,r)) 
				    {
					   for (int i=1;i<=c[yao[step-1]];i++) b[a[yao[step-1]][i]]++;
					   dfs(step+1);
					   for (int i=1;i<=c[yao[step-1]];i++) b[a[yao[step-1]][i]]--;
				    }
	}
}
void zdfs(int step)
{
	int r;
	if (step>p)
	{
		pd();
	}else
	{
		if (yao[step]==0)
		{
			for (r=1;r<=n;r++)
			{
				if (step==1)
				{
					yao[1]=r;b[r]++;
					zdfs(step+1);
					yao[1]=0;b[r]--;
				}else
				{
					if (keyi(r,yao[step+1],yao[step-1])&&hh(step,r))
					{
						jia(yao[step-1]);yao[step]=r;
						zdfs(step+1);
						jian(yao[step-1]);yao[step]=0;
					}
				}
			}
		}else
			if (keyi1(yao[step],yao[step+1],yao[step-1]))
				if (hh(step,r)) 
				   {
					   for (int i=1;i<=c[yao[step-1]];i++) b[a[yao[step-1]][i]]++;
					   zdfs(step+1);
					   for (int i=1;i<=c[yao[step-1]];i++) b[a[yao[step-1]][i]]--;
				   }
	}
}
int main()
{
	init();
	dfs(1);
	cout<<ans<<endl;
	zdfs(1);
	return 0;
}