比赛 20120914 评测结果 C
题目名称 著名医生的药方 最终得分 0
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-09-14 21:56:53
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;
int m,n,r[600];
char e[3000];
int w[600][600]={0};
int w1[600][600]={0};
bool use[600][600]={0};
bool use1[600][600]={0};
int num[600]={0},num1[600]={0};
int answer=0;
bool used[600]={0},su[600]={0};
vector<int>ans;
void dfs(int x);
int main()
{
	freopen ("doctor.in","r",stdin);
	freopen ("doctor.out","w",stdout);
	scanf("%d\n",&m);
	for (int i=1;i<=m;i++)
	{
		gets(e);
		int lq;
		lq=strlen(e);
		int tmp=0,ji=0;
		for (int j=0;j<lq;j++)
		{
			if (e[j]>='0'&&e[j]<='9')
			{
				tmp=tmp*10+(e[j]-'0');
			}
			if (e[j]==' ')
			{
				w[i][ji]=tmp;
				w1[tmp][num1[tmp]]=i;
				use1[tmp][i]=1;
				use[i][tmp]=1;
				num1[tmp]++;
				ji++;
				tmp=0;
			}
		}
		w1[tmp][num1[tmp]]=i;
		num1[tmp]++;
		use1[tmp][i]=1;
		w[i][ji]=tmp;
		use[i][tmp]=1;
		ji++;
		num[i]=ji;
	}
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>r[i];
		if (r[i]!=0)
		{
			used[r[i]]=1;
			su[r[i]]=1;
		}
	}
	if (n==1)
	{
		cout<<1<<endl<<1;
		return 0;
	}
	dfs(0);
	cout<<answer<<endl;
	int ttt=0;
	for (int i=0;i<answer;i++)
	{
		for (int j=0;j<n;j++)
		{
			cout<<ans[ttt+j]<<' ';
		}
		ttt+=n;
		cout<<endl;
	}
	return 0;
}
void dfs(int x)
{
	if (x==n)
	{
		for (int i=0;i<n;i++)
			ans.push_back(r[i]);
		answer++;
	}
	else
	{
		if (r[x]!=0)
		{
			for (int j=0;j<num[r[x-1]];j++)
			{
				used[w[r[x-1]][j]]=1;
			}
			dfs(x+1);
			for (int j=0;j<num[r[x-1]]&&!su[w[r[x-1]][j]];j++)
			{
				bool op=0;
				for (int i=0;i<x;i++)
				{
					if (w[r[x-1]][j]==r[i])
						op=1;
				}
				if (op==1)
					continue;
				used[w[r[x-1]][j]]=0;
			}
		}
		else
		{
			int temp=0;
			int tp[600]={0};
			bool p=1;
			if (x==0&&r[x+1]!=0&&p)
			{
				for (int i=1;i<=num1[r[x+1]];i++)
				{
					tp[i]=w1[r[x+1]][i-1];
				}
				temp=num1[r[x+1]];
				p=0;
			}
			if (x==0&&r[x+1]==0&&p)
			{
				for (int i=1;i<=n;i++)
				{
					tp[i]=i;
				}
				temp=n;
				p=0;
			}
			if (x==n-1&&p)
			{
				for (int i=1;i<=num[r[x-1]];i++)
				{
					tp[i]=w[r[x-1]][i-1];
				}
				temp=num[r[x-1]];
				p=0;
			}
			if (x!=0&&r[x+1]!=0&&p)
			{
				for (int i=1;i<=num1[r[x+1]];i++)
				{
					if (use[r[x-1]][w1[r[x+1]][i-1]])
					{
						tp[temp]=w1[r[x+1]][i-1];
						temp++;
					}
				}
				p=0;
			}
			if (x!=0&&r[x+1]==0&&p)
			{
				for (int i=1;i<=num[r[x-1]];i++)
				{
					tp[i]=w[r[x-1]][i-1];
				}
				temp=num[r[x-1]];
				p=0;
			}
			for (int i=1;i<=temp;i++)
			{
				if (used[tp[i]])
					continue;
				if (x!=0)
				{
					for (int j=0;j<num[r[x-1]];j++)
					{
						used[w[r[x-1]][j]]=1;
					}
				}
				r[x]=tp[i];
				used[tp[i]]=1;
				dfs(x+1);
				r[x]=0;
				used[tp[i]]=0;
			}
			for (int j=0;j<num[r[x-1]]&&!su[w[r[x-1]][j]];j++)
			{
				bool op=0;
				for (int i=0;i<x;i++)
				{
					if (w[r[x-1]][j]==r[i])
						op=1;
				}
				if (op==1)
					continue;
				used[w[r[x-1]][j]]=0;
			}
		}
	}
}