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