复杂的按钮(button.pas)

    【题目描述】

    小k在遗迹探险时遇到了n个按钮，刚开始所有按钮都处于开状态，小k的经验告诉他把所有按钮都关上会有“好事”发生，可是有些按钮按下时会让其他一些已经闭合的按钮弹开。经过研究，每个按钮都对应着一个固定的弹开集合，这个按钮按下时，弹开集合中所有的按钮都会变为开状态。现在小k想知道是否能让所有的按钮变为闭状态。如果能，打印最少步数以及方案。否则，打“no solution"。

    【输入格式】

第一行一个整数n，表示n个按钮

接下来n行，表示编号为l到n个按钮 的弹开集合

    格式为mi，B1B2 B3…Bmi。

    表示编号为i的按钮按下，会让编号为B1B2 B3…Bmi 的按钮弹开(注：其中不会出现重 复)

    【输出格式】

    如果无解，输出"no solution"．

    否则，第一行输出最少步数ans，第二行输出用空格分开的ans个数，表示按顺序按下

编号为这些数的按钮就可以解决。

    如果有多种方案，输出字典序最小的方案。

    【样例输入】button.in

    6

    2 2 3

    0

    2 4 5

    0

    0

    0

    【样例输出】button.out

    6

    l 2 3 4 5 6

    【数据范围】

    l≤n≤30000

    令M=m1+m2+…+mn

    0≤M≤1000000

逆向思考，当按下最后一个按钮时，不能有任何按钮弹起

按下倒数第二个按钮时，最多让最后一个按钮弹起

按下倒数第三个按钮时，最多让后两个弹起

........................

按下第二个按钮时，不能让第一个弹起

按下第一个按钮时，可以让任何按钮弹起

明显必须按下Ｎ次按钮，且弹起的按钮必须在它之后按下

可以用拓扑排序生成序列

用堆优化，每次堆中的元素保证入度都为０，且堆首的元素编号最小

program fdfd;
var n,i,j,k,x,y:longint;
    b:array[1..30000,0..90] of longint;
    ru,ans:array[1..30000] of longint;
    vis:array[1..30000] of boolean;

    h:array[0..30000] of longint;
    size:longint;
procedure sdown;
var y,z,v:longint;
begin
     y:=1; z:=y*2; v:=h[1];
     while (z<=size) do
     begin
       if z<size then
       if h[z+1]< h[z] then z:=z+1;
       if h[z]>v then break;
       h[y]:=h[z]; y:=z; z:=y*2;
     end;
     h[y]:=v;
end;
procedure sink(p:longint);
var y,z,v:longint;
begin
    y:=p; z:=y div 2; v:=h[y] ;
    while (h[z]>v)and(z>=1) do
    begin
      h[y]:=h[z];
      y:=z; z:=y div 2;
    end;
    h[y]:=v;
end;
begin
assign(input,'button.in');assign(output,'button.out');
reset(input); rewrite(output);
fillchar(b,sizeof(b),0);
fillchar(ru,sizeof(ru),0);
readln(n);
for i:=1 to n do
begin
    read(x);
    for j:=1 to x do
    begin
       read(y);
       inc(b[i,0]) ;
       b[i,b[i,0]] :=y;
       inc(ru[y]);
    end;
    readln;
end;
size:=0;
for i:=1 to n do
if ru[i]=0 then
begin
    inc(size);
    h[size]:=i;
end;
fillchar(vis,sizeof(vis),false);
for i:=1 to n do
begin
    k:=h[1];
    if vis[k] then
      begin
        writeln('no solution');
        halt;
      end;
    vis[k]:=true;
    ans[i]:=k;
    h[1]:=h[size]; dec(size); sdown;
    for j:=1 to b[k,0] do
    if vis[b[k,j]] then
      begin
        writeln('no solution');
        halt;
      end
    else
    begin
    dec(ru[b[k,j]]);
    if ru[b[k,j]] =0 then
      begin
        inc(size) ;
        h[size]:=b[k,j];
        sink(size);
      end;
    end;
end;
writeln(n);
for i:=1 to n-1 do write(ans[i], ' ') ;
writeln(ans[n]);
close(input);
close(output);
end．