来自"NOCOW"

The Prufer code 时间限制: 2.0 s 内存限制: 1 000 KB

program cao;
const
  maxn=10000;
 
type
  node=record
    v,next:longint;
  end;
 
  Theap=object
    data:array[0..maxn] of longint;
    total:longint;
    procedure init;
    procedure insert(v:longint);
    procedure deletetop;
    function getmin:longint;
  end;
 
var
  heap:Theap;
  data,times,ans,head:array[0..maxn] of longint;
  t:array[0..maxn*2] of node;
  a,b,c,d,e,f,g,h,i,j,k,l,n,m,p,q,total,tmp:longint;
 
procedure swap(var a,b:longint);
begin
  tmp:=a;
  a:=b;
  b:=tmp;
end;
 
procedure qsort(left,right:longint);
var
  i,j,x:longint;
begin
  i:=left;
  j:=right;
  x:=ans[(i+j) shr 1];
  while i<j do
  begin
    while ans[i]<x do inc(i);
    while ans[j]>x do dec(j);
    if i<=j then
    begin
      swap(ans[i],ans[j]);
      inc(i);
      dec(j);
    end;
  end;
  if i<right then qsort(i,right);
  if j>left then qsort(left,j);
end;
 
procedure Theap.init;
begin
  total:=0;
end;
 
procedure Theap.insert(v:longint);
var
  i:longint;
begin
  inc(total);
  data[total]:=v;
  i:=total;
  while (i>1)and(data[i]<data[i shr 1]) do
  begin
    swap(data[i],data[i shr 1]);
    i:=i shr 1;
  end;
end;
 
procedure Theap.deletetop;
var
  i,j:longint;
begin
  data[1]:=data[total];
  dec(total);
  i:=1;
  while (i shl 1)<=total do
  begin
    j:=i shl 1;
    if (j+1<=total)and(data[j+1]<data[j]) then inc(j);
    if data[i]>data[j] then
    begin
      swap(data[i],data[j]);
      i:=j;
    end
    else break;
  end;
end;
 
function Theap.getmin:longint;
begin
  exit(data[1]);
end;
 
procedure init;
begin
  n:=0;
  while not(seekeof) do
  begin
    inc(n);
    read(data[n]);
  end;
end;
 
procedure main;
begin
  for i:=1 to n do
    inc(times[data[i]]);
  heap.init;
  for i:=1 to n+1 do
    if times[i]=0 then
      heap.insert(i);
  for i:=1 to n do
  begin
    k:=heap.getmin;
    inc(total);
    t[total].v:=k;
    t[total].next:=head[data[i]];
    head[data[i]]:=total;
    inc(total);
    t[total].v:=data[i];
    t[total].next:=head[k];
    head[k]:=total;
    dec(times[data[i]]);
    heap.deletetop;
    if times[data[i]]=0 then heap.insert(data[i]);
  end;
end;
 
procedure print;
begin
  for i:=1 to n+1 do
  begin
    k:=0;
    j:=head[i];
    while j<>0 do
    begin
      inc(k);
      ans[k]:=t[j].v;
      j:=t[j].next;
    end;
    qsort(1,k);
    write(i,':');
    for j:=1 to k do
      write(' ',ans[j]);
    writeln;
  end;
end;
 
begin
  init;
  main;
  print;
end.
//http://www.withflying.com/?p=131
//http://www.withflying.com

---

哥们，我觉得你好像写麻烦了……

我觉得应该先把给出的数据扫一遍，保存到一个数组里，得到n的值，顺便分别以节点的儿子数目和节点编号为第一第二关键字建一个最小堆。

然后从前往后再扫描一遍输入，对于输入中的每一个节点，将最小堆中最顶端的节点标记为前者的儿子并将前者的儿子数目减1，上浮。

居然要用到邻接表。注意，注意，我没有说过我的算法一定是正确的，求严格的证明/证伪过程。--Wecing 18:06 2010年5月8日 (CST)

---

同上 因为我用的就是这种方法 一次AC

证明其实也没什么好证明的 相当于是像拓扑排序一样从底端拓扑到上端 如果对一个有向无环图让我们每次都以最小点拓扑 答案即是这个 相当于给出拓扑输出让我们还原有向图。

弱弱的代码奉上：

program cyd;
  var
    p:array[1..7500]of boolean;
    d,e:array[1..7500]of integer;
    heap:array[1..7500]of integer;
    tou,next,f,po:array[1..7500]of integer;
    hp,i,j,k,l,m,n,a,c,tot:longint;
  procedure swap(var a,b:integer);
    var
      tmp:longint;
    begin
      tmp:=a;
      a:=b;
      b:=tmp;
    end;
  procedure qsort(l,r:longint);
    var
      tl,tr,mid,tmp:longint;
    begin
      tl:=l; tr:=r; mid:=d[(l+r)div 2];
      repeat
        while d[tl]>mid do inc(tl);
        while d[tr]<mid do dec(tr);
        if tl<=tr then
          begin
            swap(d[tl],d[tr]);
            inc(tl); dec(tr);
          end;
        until tl>tr;
      if l<tr then qsort(l,tr);
      if r>tl then qsort(tl,r);
    end;
  procedure add(a:longint);
    var
      x,y:longint;
    begin
      inc(hp);
      heap[hp]:=a;
      x:=hp;
      while x>1 do
        begin
          y:=x div 2;
          if heap[x]<heap[y] then swap(heap[x],heap[y]) else break;
          x:=y;
        end;
    end;
  procedure del;
    var
      x,y:longint;
    begin
      if hp=1 then begin dec(hp); exit; end;
      heap[1]:=heap[hp];
      dec(hp);
      x:=1;
      while x*2<=hp do
        begin
          y:=x*2;
          if (y+1<=hp)and(heap[y+1]<heap[y]) then inc(y);
          if heap[y]<heap[x] then swap(heap[y],heap[x]) else break;
          x:=y;
        end;
    end;
  begin
    while not eof do
      begin
        read(a);
        if a=0 then break;
        inc(n);
        d[n]:=a;
        inc(e[a]);
        p[a]:=true;
      end;
    inc(n);
    for i:=1 to n do
      if not p[i] then add(i);
    for i:=1 to n-1 do
      begin
        a:=heap[1];
        del;
        inc(tot);
        po[tot]:=a;
        next[tot]:=tou[d[i]];
        tou[d[i]]:=tot;
        f[a]:=d[i];
        dec(e[d[i]]);
        if e[d[i]]=0 then add(d[i]);
      end;
    for i:=1 to n do
      begin
        write(i,': ');
        j:=tou[i];
        k:=0;
        while j<>0 do
          begin
            inc(k);
            d[k]:=po[j];
            j:=next[j];
          end;
        if f[i]<>0 then begin inc(k); d[k]:=f[i]; end;
        qsort(1,k);
        for j:=k downto 2 do
          write(d[j],' ');
        writeln(d[1]);
      end;
  end.

stl表示毫无鸭梨

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
using std::sort;
using std::set;
const int maxn=7510;
int n=1,t,tot=0,a[maxn],e[maxn]={0},out[maxn];
int h[maxn]={0},node[maxn<<1],next[maxn<<1];
set<int> x;
void add(int a,int b)
{
    node[++tot]=b;
    next[tot]=h[a];
    h[a]=tot;
}
int main()
{
    int i,j;
    while (scanf("%d",&a[n++]) != EOF);
    --n;
    for (i=1;i<n;++i)  ++e[a[i]];
    for (i=1;i<=n;++i)
        if (!e[i])
            x.insert(i);
    for (i=1;i<n;++i)
    {
        t=*x.begin();
        x.erase(t);
        add(t,a[i]);
        add(a[i],t);
        if (!(--e[a[i]]))  x.insert(a[i]);
    }
    for (i=1;i<=n;++i)
    {
        printf("%d:",i);
        for (tot=0,j=h[i];j;j=next[j])
            out[tot++]=node[j];
        sort(out,out+tot);
        for (j=0;j<tot;++j)  printf(" %d",out[j]);
        printf("\n");
    }
    return 0;
}
//by zzy