代码大意是深搜，自锁/回到1/必经处形成环的情况直接输poor boy退出，flag记录正在搜索的记忆编号，state记录是否被回忆过，queue记录搜索历程，怎么就不对啊就不对啊……

program rq241;

var

link:array[1..10,1..10] of boolean;

n,i:integer;

queue:array[1..10] of integer;

queuep:integer;

state:array[1..10] of boolean;

flag:array[1..10] of boolean;

z:longint;

procedure init;

var

i,j,l,c:integer;

begin

readln(n);

fillchar(link,sizeof(link),false);

for i:=1 to n do

begin

read(c);

for j:=1 to c do

begin

read(l);

link[i][l]:=true;

end;

readln;

end;

queuep:=0;

fillchar(state,sizeof(state),false);

fillchar(flag,sizeof(flag),false);

end;

procedure dfs(x:integer);

var i:integer;

begin

flag[x]:=true;

if (x=1)and(z<>0) then begin writeln('What a poor boy!');halt;end;

inc(z);

if link[x][x] then begin writeln('What a poor boy!');halt;end;

for i:=1 to n do

if (link[x][i])and(not state[i]) then

if flag[i] then begin writeln('What a poor boy!');halt;end

else dfs(i);

inc(queuep);

queue[queuep]:=x;

state[i]:=true;

flag[x]:=false;

end;

begin

z:=0;

init;

dfs(1);

for i:=1 to queuep-1 do write(queue[i],' ');

writeln(queue[queuep]);

end.

额……

我就剩这点分了……大家给个回复呐……

rp++

觉得方法不错，我这么没想到？

动态规划！

哦哦！我明白了！谢谢楼主

我定帮你！

楼主我帮你看看，用动归

楼主你看看

一开始，用DFS做的，莫名的wa了4个点。之后才AC。我问了几个同学，似乎都出现了这个情况

哇啊啊啊啊啊拓扑排序怎么也不行……

floyd计算1的前驱然后拓扑排序……为什么WA80……

program rq241;

var

link:array[1..10,1..10] of boolean;

n:integer;

waitsort:array[1..10] of integer;

waitsortp:integer;

procedure init;

var i,j:integer;

c,p:integer;

begin

fillchar(link,sizeof(link),false);

readln(n);

for i:=1 to n do

begin

read(p);

for j:=1 to p do

begin

read(c);

link[c][i]:=true;

end;

readln;

end;

end;

procedure floyd;

var i,j,k:integer;

begin

for i:=1 to n do

for j:=1 to n do

for k:=1 to n do

if (link[j][i])and(link[i][k]) then link[j][k]:=true;

end;

procedure pick;

var i,j:integer;

begin

waitsortp:=0;

for i:=1 to n do

for j:=1 to n do

if (link[i][j])and(link[j][i]) then

begin

writeln('What a poor boy!');

halt;

end;

for i:=2 to n do

if link[i][1] then

begin

inc(waitsortp);

waitsort[waitsortp]:=i;

end;

end;

procedure tpsort;

var i,j,k:integer;

flag:array[1..10] of boolean;

tf:boolean;

begin

fillchar(flag,sizeof(flag),false);

for i:=1 to waitsortp do flag[waitsort[i]]:=true;

for i:=1 to waitsortp do

begin

for j:=1 to waitsortp do

if flag[waitsort[j]] then

begin

tf:=true;

for k:=1 to n do if link[k][waitsort[j]] then tf:=false;

if tf then

begin

flag[waitsort[j]]:=false;

for k:=1 to n do link[waitsort[j]][k]:=false;

write(waitsort[j],' ');

break;

end;

end;

end;

writeln('1');

end;

begin

init;

floyd;

pick;

tpsort;

end.

过啦过啦分分……

状态: Accepted

测评机： Xeost[5]

得分： 100分 [我要评价一下题目~]

提交日期： 2012-6-29 22:29:00

有效耗时： 1654毫秒

测试结果1: 通过本测试点|有效耗时187ms

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时171ms

测试结果5: 通过本测试点|有效耗时156ms

测试结果6: 通过本测试点|有效耗时172ms

测试结果7: 通过本测试点|有效耗时156ms

测试结果8: 通过本测试点|有效耗时172ms

测试结果9: 通过本测试点|有效耗时156ms

测试结果10: 通过本测试点|有效耗时156ms