比赛 |
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;
}