记录编号	42190	评测结果	AAAAAAAA
题目名称	[ZSTU 2579] 著名医生的药方	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.350 s
提交时间	2012-09-17 08:42:36	内存使用	1.79 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int N = 500 + 10;
int n, p, total;
int suc[N][N], obj[N], dt[N], limit1[N];
bool used[N], limit2[N][N], print;
bool is_succ(int x, int y) {
    for(int i=1; i<=suc[x][0]; i++)
        if(suc[x][i] == y)
            return 1;
    return 0;
}
int is_one_pred(int x) {
    int r = 0, k = 0;
    for(int i=1; i<=n; i++) if(is_succ(i, x)) {
        if(!k) k = i; else return r;
    } return r = k;
}
bool init() {
    total = 0;
    dt[0] = 0;
    for(int i=2; i<p; i++)
        if(obj[i]) {
            int k = is_one_pred(obj[i]);
            if(!k) continue;
            for(int j=i+1; j<=p; j++)
                if(is_succ(k, obj[j]))
                    return 0;
        }
    memset(used, 1, sizeof(used));
    for(int i=1; i<=p; i++)
        if(obj[i]) used[obj[i]] = 0;
    memset(limit1, 0, sizeof(limit1));
    memset(limit2, 1, sizeof(limit2));
    for(int i=p-1; i>0; i--) {
        if(obj[i+1] && obj[i])
            if(!is_succ(obj[i], obj[i+1]))
                return 0;
        memcpy(limit2[i], limit2[i+1], sizeof(limit2[i]));
        if(i+2 > p) continue;
        if(obj[i+2])
            for(int j=1; j<=n; j++)
                if(limit2[i][j] && is_succ(j, obj[i+2]))
                    limit2[i][j] = 0;
        if(obj[i] && !limit2[i][obj[i]])
            return 0;
    }
    return 1;
}
void save() {
    if(!print) total++;
    else {
        for(int j=1; j<p; j++)
            printf("%d ", dt[j]);
        printf("%d\n", dt[p]);
    }
}
void limit_inc(int x) {
    for(int i=1; i<=suc[x][0]; i++)
        limit1[suc[x][i]]++;
}
void limit_dec(int x) {
    for(int i=1; i<=suc[x][0]; i++)
        limit1[suc[x][i]]--;
}
void DFS(int z) {
    if(z > p) { save(); return; }
    if(obj[z]) {
        if(z > 1 && !obj[z-1])
            if(!is_succ(dt[z-1], obj[z])) return;
        if(z > 1) limit_inc(dt[z-1]);
        dt[z] = obj[z];
        DFS(z+1);
        if(z > 1) limit_dec(dt[z-1]);
    } else {
        for(int i=1; i<=suc[dt[z-1]][0]; i++) {
            int k = suc[dt[z-1]][i];
            if(used[k] && limit2[z][k] && !limit1[k]) {
                if(z > 1) limit_inc(dt[z-1]);
                used[dt[z] = k] = 0;
                DFS(z+1);
                used[k] = 1;
                if(z > 1) limit_dec(dt[z-1]);
            }
        }
    }
}
int main() {
    freopen("doctor.in", "r", stdin);
    freopen("doctor.out", "w", stdout);
    char s[N], t[N];
    scanf("%d\n", &n);
    suc[0][0] = n;
    for(int i=1; i<=n; i++)
        suc[0][i] = i;
    for(int i=1; i<=n; i++) {
        int k = 0, x;
        memset(s, 0, sizeof(s));
        memset(t, 0, sizeof(t));
        gets(s);
        for(int j=0; s[j]; j+=strlen(t)+1) {
            sscanf(s+j, "%s", t);
            sscanf(t, "%d", &x);
            k++; suc[i][k] = x;
        } suc[i][0] = k;
    }
    scanf("%d\n", &p);
    for(int i=1; i<=p; i++)
        scanf("%d", obj+i);
    if(init()) {
        DFS(1);
        printf("%d\n", total);
        print = 1;
        DFS(1);
    } else printf("%d\n", 0);
    return 0;
}