比赛 20120914 评测结果 AAWWEEEE
题目名称 著名医生的药方 最终得分 25
用户昵称 cqw 运行时间 15.771 s
代码语言 C++ 内存使用 4.60 MiB
提交时间 2012-09-16 17:54:56
显示代码纯文本
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("doctor.in");
ofstream fout("doctor.out");
int a[501][501],yao[501],ans[501],n,p,asum=0,as[501][501],ct[501];string st="";
class cyn
{
public:int b[501];
};
cyn bl;
vector<cyn> syn;
void init()
{
	fin>>n;int i,j,s=0;
	getline(fin,st);
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) a[i][j]=0;
	for (i=1;i<=n;i++)
	{
		bl.b[i]=false;ct[i]=0;
		getline(fin,st);s=0;
		j=0;while (j<st.length()&&(st[j]>='0'&&st[j]<='9'||st[j]==' '))
		{
			if (st[j]==' ') 
			    {a[i][s]=1;s=0;j++;} 
			else
			    s=s*10+(int(st[j++])-48);
		}a[i][s]=1;
	}
	fin>>p;for (i=1;i<=p;i++) 
	{   fin>>yao[i];
	    if (yao[i]!=0) {bl.b[yao[i]]=-900000;ct[yao[i]]=i;}
	}
}
void print()
{
	asum++;
	for (int i=1;i<=p;i++) as[asum][i]=ans[i];
}
bool pd(int x,int y,int step)
{
	for (int i=1;i<=n;i++)
		if (a[x][i]==1&&i!=y&&ct[i]>=step) return false;
	return true;
}
void dfs(int step,int x)
{
	int r;
	if (step>p) print();else
	{
		if (yao[step]!=0) 
		{
			if (a[ans[step-1]][yao[step]]==0) return;
			syn.push_back(bl);ans[step]=r;
			for (int i=1;i<=n;i++) if (a[ans[step-1]][i]==1) bl.b[i]++;
			ans[step]=yao[step];
			dfs(step+1,yao[step]);
			bl=syn.at(syn.size()-1);syn.pop_back();
		}else
		{
			for (r=1;r<=n;r++)
			{
				if (bl.b[r]==false&&a[ans[step-1]][r]==1)
				{
					if (pd(ans[step-1],r,step))
					{syn.push_back(bl);ans[step]=r;
					for (int i=1;i<=n;i++) if (a[ans[step-1]][i]==1) bl.b[i]++;
					dfs(step+1,r);
					bl=syn.at(syn.size()-1);syn.pop_back();}
				}
			}
		}
	}
}
void zprint()
{
	fout<<asum<<endl;
	for (int i=1;i<=asum;i++)
	{
		for (int j=1;j<p;j++) fout<<as[i][j]<<' ';
		fout<<as[i][p]<<endl;
	}
}
int main()
{
	init();
	if (yao[1]==0)
	{
	    for (int i=1;i<=n;i++)
		{
			if (bl.b[i]==false)
			{
				ans[1]=i;bl.b[i]=true;
				dfs(2,i);
			}bl.b[i]=false;
		}
	}else
	{
        ans[1]=yao[1];
		dfs(2,yao[1]);
	}		
	zprint();
	return 0;
}